Submission #753634

#TimeUsernameProblemLanguageResultExecution timeMemory
753634amirhoseinfar1385Synchronization (JOI13_synchronization)C++17
20 / 100
8085 ms179320 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=300000+10; struct yal{ vector<pair<int,int>>w,dp,link; int u,v; int getad(int fu){ int ret=(u^v^fu); return ret; } }; yal alled[maxn]; vector<int>adj[maxn],fake,bal[maxn],khod[maxn]; int fn,n,m,res[maxn],vis[maxn],sz[maxn],azb[maxn],high[maxn],timea,q,par[maxn]; vector<pair<int,pair<int,int>>>fakea; pair<int,int>stf[maxn]; int kaf=(1<<17); struct segment{ set<pair<int,int>> seg[(1<<18)]; vector<int>v; void clear(){ for(auto x:v){ seg[x].clear(); } v.clear(); } void upd(int i,int l,int r,int tl,int tr,int av,int dov=-1){ if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ v.push_back(i); /*if(dov==-1){ if(high[seg[i]]<high[av]){ seg[i]=av; } } else{ if(seg[i]==av){ seg[i]=dov; } }*/ if(dov==-1){ seg[i].insert(make_pair(high[av],av)); } else{ seg[i].erase(make_pair(high[av],av)); } return ; } int m=(l+r)>>1; upd((i<<1),l,m,tl,tr,av,dov); upd((i<<1)^1,m+1,r,tl,tr,av,dov); return ; } int pors(int i){ if(i==0){ return 0; } int ret=pors((i>>1)); if((int)seg[i].size()>0&&high[ret]<(*seg[i].rbegin()).first){ ret=(*seg[i].rbegin()).second; } return ret; } }seg; void dfs(int u,int para=0,int az=0){ fake.push_back(u); high[u]=high[para]+1; azb[u]=az; sz[u]=1; if(para==0){ high[u]=1; timea=0; } else{ sz[u]+=(int)alled[par[u]].w.size(); } timea++; stf[u].first=timea; for(auto xx:adj[u]){ int x=alled[xx].getad(u); if(vis[x]==1||x==para){ continue; } par[x]=xx; if(para==0){ bal[x].clear(); dfs(x,u,x); } else{ dfs(x,u,az); } sz[u]+=sz[x]; } stf[u].second=timea; } int finds(int u,int para=0){ for(auto xx:adj[u]){ int x=alled[xx].getad(u); if(vis[x]==0&&x!=para&&sz[x]*2>fn){ return finds(x,u); } } return u; } bool cmp(pair<int,pair<int,int>> a,pair<int,pair<int,int>>b){ if(a.first!=b.first){ return a.first<b.first; } if(a.second.second!=b.second.second){ return a.second.second<b.second.second; } if(a.second.second==1){ return high[a.second.first]<high[b.second.first]; } else{ return high[a.second.first]>high[b.second.first]; } } void solve(int u){ dfs(u); fake.clear(); fn=sz[u]; int v=finds(u); fake.clear(); dfs(v); seg.clear(); fakea.clear(); for(auto x:fake){ if(x==v){ continue; } alled[par[x]].link.clear(); for(auto y:alled[par[x]].w){ fakea.push_back(make_pair(y.first,make_pair(x,1))); fakea.push_back(make_pair(y.second,make_pair(x,2))); } } sort(fakea.begin(),fakea.end(),cmp); for(auto x:fake){ seg.upd(1,0,kaf-1,stf[x].first+1,stf[x].second,x); } for(int i=0;i<(int)fakea.size();i++){ int p=seg.pors(kaf+stf[fakea[i].second.first].first); if(fakea[i].second.second==1){ alled[par[fakea[i].second.first]].link.push_back(make_pair(p,v)); int ba=p; seg.upd(1,0,kaf-1,stf[fakea[i].second.first].first+1,stf[fakea[i].second.first].second,fakea[i].second.first,ba); } else{ alled[par[fakea[i].second.first]].link.back().second=p; seg.upd(1,0,kaf-1,stf[fakea[i].second.first].first+1,stf[fakea[i].second.first].second,fakea[i].second.first); } } for(auto x:fake){ if(x==v){ khod[v].push_back(0); continue; } for(int i=0;i<(int)alled[par[x]].w.size();i++){ int linky1=alled[par[x]].link[i].first; int p=lower_bound(alled[par[linky1]].w.begin(),alled[par[linky1]].w.end(),make_pair(alled[par[x]].w[i].first,-1))-alled[par[linky1]].w.begin(); if(linky1==v){ alled[par[x]].dp[i].first=alled[par[x]].w[i].first; } else if(p==alled[par[linky1]].w.size()){ alled[par[x]].dp[i].first=m+10; } else{ alled[par[x]].dp[i].first=alled[par[linky1]].dp[p].first; } int linky2=alled[par[x]].link[i].second; p=lower_bound(alled[par[linky2]].w.begin(),alled[par[linky2]].w.end(),make_pair(alled[par[x]].w[i].second,-1))-alled[par[linky2]].w.begin(); p--; if(linky2==v){ alled[par[x]].dp[i].second=alled[par[x]].w[i].second; } else if(p<0){ alled[par[x]].dp[i].second=-1; } else{ alled[par[x]].dp[i].second=alled[par[linky2]].dp[p].second; } } if(alled[par[x]].w.size()==0){ continue; } int ff=alled[par[x]].dp[0].first; if(ff>m+2){ continue; } khod[v].push_back(ff); bal[azb[x]].push_back(ff); } sort(khod[v].begin(),khod[v].end()); for(auto xx:adj[v]){ int x=alled[xx].getad(v); if(vis[x]==0){ sort(bal[x].begin(),bal[x].end()); } } for(auto x:fake){ if(x==v){ res[x]+=khod[v].size(); continue; } if((int)alled[par[x]].w.size()==0){ continue; } int ff=alled[par[x]].dp.back().second; int p=upper_bound(khod[v].begin(),khod[v].end(),ff)-khod[v].begin(); p--; res[x]+=p+1; p=upper_bound(bal[azb[x]].begin(),bal[azb[x]].end(),ff)-bal[azb[x]].begin(); p--; res[x]-=p+1; } vis[v]=1; for(auto xx:adj[v]){ int x=alled[xx].getad(v); if(vis[x]==0){ solve(x); } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("inp.txt","r",stdin); // freopen("out.txt","w",stdout); cin>>n>>m>>q; for(int i=1;i<=n-1;i++){ cin>>alled[i].u>>alled[i].v; adj[alled[i].u].push_back(i); adj[alled[i].v].push_back(i); } for(int i=1;i<=m;i++){ int u; cin>>u; if((int)alled[u].w.size()==0||alled[u].w.back().second!=-1){ alled[u].w.push_back(make_pair(i,-1)); } else{ alled[u].w.back().second=i; } } for(int i=1;i<n;i++){ if((int)alled[i].w.size()>0&&alled[i].w.back().second==-1){ alled[i].w.back().second=m+1; } alled[i].dp.resize((int)alled[i].w.size()); } solve(1); for(int i=0;i<q;i++){ int u; cin>>u; cout<<res[u]<<"\n"; } }

Compilation message (stderr)

synchronization.cpp: In function 'void solve(int)':
synchronization.cpp:172:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |    else if(p==alled[par[linky1]].w.size()){
      |            ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...