제출 #278488

#제출 시각아이디문제언어결과실행 시간메모리
278488stefanbalaz2무제 (POI11_dyn)C++14
50 / 100
3074 ms65536 KiB
/* */ #include<bits/stdc++.h> #include<set> using namespace std; #define pb push_back #define ff first #define ss second #define ll long long typedef pair<int,int> pii; typedef set<int>::iterator sit; const int maxn=3e5+10; pii dp2[maxn]; int d[maxn],n,ind[maxn],m,lazy[maxn]; vector<pii>stek[maxn],dp1[maxn]; vector<int>vect[maxn]; void ins(int x,int val,int id){ ///printf("%d ALZY\n",lazy); if(stek[x].size()==0){ stek[x].pb({-lazy[x],id}); lazy[x]+=val; return; } if(stek[x].back().ss==id)lazy[x]+=val; else{ stek[x].pb({-lazy[x],id}); lazy[x]+=val; } /// printf("%d ALZY\n",lazy); } void ers(int x,int id){ ///printf("%d ALZY22\n",lazy); while(stek[x].size() && stek[x].back().ss>=id){ lazy[x]-=stek[x].back().ff+lazy[x]; stek[x].pop_back(); } ///printf("%d ALZY22\n",lazy); return; } int get_dp(int x,int id){ if(id>=(int)dp1[x].size())return 1e9; id=max(id,0); int l=0; int r=stek[x].size()-1; int ret=-1,sr; while(l<=r){ sr=(l+r)/2; if(stek[x][sr].ss>=id){ ret=sr; r=sr-1; } else l=sr+1; } int val=0; if(ret!=-1)val=stek[x][ret].ff+lazy[x]; ///printf("%d %d %d JOOOJ\n",dp1[x][id].ff,val,lazy[x]); return dp1[x][id].ff+val; } void ispis(int x){ for(int i=dp1[x].size()-1;i>=0;i--)printf("%d %d | ",dp1[x][i].ff,dp1[x][i].ss); printf("\n"); } void go(int x,int prv,int val){ ///printf("%d %d AAAA\n",x,prv); ind[x]=x; for(int j=0;j<vect[x].size();j++){ int id=vect[x][j]; if(id==prv)continue; go(id,x,val); if(dp1[ind[x]].size()<dp1[ind[id]].size())swap(ind[x],ind[id]); ///printf("%d IDIDIDID\n",id); ///if(dp1[ind[x]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[x]].ff,dp2[ind[x]].ss,dp1[ind[x]][0].ff,dp1[ind[x]][0].ss,dp1[ind[x]][1].ff,dp1[ind[x]][1].ss); ///if(dp1[ind[id]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[id]].ff,dp2[ind[id]].ss,dp1[ind[id]][0].ff,dp1[ind[id]][0].ss,dp1[ind[id]][1].ff,dp1[ind[id]][1].ss); if(dp1[ind[id]].size()==0)continue; /// merge trees /// dp2 pii pom; pom={dp2[ind[x]].ff+dp2[ind[id]].ff,min(dp2[ind[x]].ss,dp2[ind[id]].ss)}; pom=min(pom,{dp2[ind[x]].ff+get_dp(ind[id],dp1[ind[id]].size()-(val-dp2[ind[x]].ss-2)-2),dp2[ind[x]].ss}); pom=min(pom,{dp2[ind[id]].ff+get_dp(ind[x],dp1[ind[x]].size()-(val-dp2[ind[id]].ss-2)-2),dp2[ind[id]].ss}); ///dp1 int cnt1=0,cnt2=0; int ind1=dp1[ind[x]].size()-1; int ind2=dp1[ind[id]].size()-1; for(int i=dp1[ind[id]].size()-1;i>=max(0,(int)dp1[ind[id]].size()-val-1);i--){ cnt1=dp1[ind[x]][ind1].ss; cnt2=dp1[ind[id]][ind2].ss; ers(ind[x],ind1); ers(ind[id],ind2); dp1[ind[x]][ind1].ss=0; dp1[ind[id]][ind2].ss=0; dp1[ind[x]][ind1].ff+=cnt1; dp1[ind[id]][ind2].ff+=cnt2; dp1[ind[x]][ind1].ff+=dp1[ind[id]][ind2].ff; ///printf("%d %d | %d %d || %d\n",dp1[ind[x]][ind1].ff,dp1[ind[id]][ind2].ff,ind1,ind2,x); ind1--; ind2--; ins(ind[x],cnt1,ind1); if(ind1>0)dp1[ind[x]][ind1].ss+=cnt1; ins(ind[id],cnt2,ind2); if(ind2>0)dp1[ind[id]][ind2].ss+=cnt2; } ind2++; if(ind1>0)dp1[ind[x]][ind1].ss+=dp1[ind[id]][ind2].ff; ins(ind[x],dp1[ind[id]][ind2].ff,ind1); /// mozda ovaj na 0tom mestu mora posebno da se racuna, da li je on manji od ostalog? dp1[ind[x]][dp1[ind[x]].size()-1].ff=pom.ff; dp2[ind[x]]=pom; } ///printf("%d %d XXXXLAZYYYYY\n",lazy,x); if(dp1[ind[x]].size()==0){ if(d[x]){ dp1[ind[x]].pb({0,0}); dp1[ind[x]].pb({1,0}); dp2[ind[x]]={1,0}; } else{ dp1[ind[x]].pb({0,0}); dp1[ind[x]].pb({0,0}); dp2[ind[x]]={0,1e8}; } /*printf("%d XX\n",x); printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss); ispis(ind[x]);*/ return; } /*printf("%d XX\n",x); printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss); ispis(ind[x]);*/ dp2[ind[x]].ss++; pii pom; ///printf("%d LAZYYYYY\n",lazy); ///printf("%d %d AAAAA\n",get_dp(ind[x],dp1[ind[x]].size()-val-1),dp1[ind[x]].size()-val-1); pom={min(dp2[ind[x]].ff,get_dp(ind[x],dp1[ind[x]].size()-val-1))+1,0}; if(d[x]==0 || dp2[ind[x]].ss<=val)pom=min(pom,dp2[ind[x]]); if(pom.ff==0)pom.ss=1e8; ers(ind[x],dp1[ind[x]].size()-1); ins(ind[x],dp1[ind[x]][dp1[ind[x]].size()-1].ss,dp1[ind[x]].size()-2); if(dp1[ind[x]].size()>1)dp1[ind[x]][dp1[ind[x]].size()-2].ss=dp1[ind[x]][dp1[ind[x]].size()-1].ss; dp1[ind[x]][dp1[ind[x]].size()-1].ss=0; dp1[ind[x]][dp1[ind[x]].size()-1]={min(dp2[ind[x]].ff,pom.ff),0}; dp1[ind[x]].pb({pom.ff,0}); dp2[ind[x]]=pom; /*printf("%d XX\n",x); printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss); ispis(ind[x]);*/ } bool check(int x){ memset(dp2,0,sizeof(dp2)); for(int i=1;i<=n;i++){ dp1[i].clear(); stek[i].clear(); lazy[i]=0; } go(1,0,x); if(dp2[ind[1]].ff<=m)return true; else return false; } int main(){ ///freopen("test2.txt","r",stdin); ///freopen("out.txt","w",stdout); /// OPTIMISATION WHEN IT CANT SOLVE A SUBTREE THEN BREAK ALL scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&d[i]); ///if(n>10000)return 123; for(int i=1;i<n;i++){ int u,v; scanf("%d %d",&u,&v); vect[u].pb(v); vect[v].pb(u); } int l=0; int r=n; int sr,ret=-1; while(l<=r){ sr=(l+r)/2; ///printf("%d %d %d AAA\n",l,sr,r); if(check(sr)){ ret=sr; r=sr-1; } else l=sr+1; } ///printf("%d CEHCK\n",check(5)); ///printf("%d CEHCK\n",check(1)); printf("%d\n",ret); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

dyn.cpp: In function 'void go(int, int, int)':
dyn.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int j=0;j<vect[x].size();j++){
      |                 ~^~~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:211:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  211 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:212:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  212 |     for(int i=1;i<=n;i++)scanf("%d",&d[i]);
      |                          ~~~~~^~~~~~~~~~~~
dyn.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  217 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...