Submission #655320

#TimeUsernameProblemLanguageResultExecution timeMemory
655320600MihneaInside information (BOI21_servers)C++17
15 / 100
3595 ms86272 KiB
#include <bits/stdc++.h> using namespace std; const int N=240000+7; int n; int k; vector<pair<int, int>> gg[N]; vector<pair<int,int>> q2[N]; vector<int> q1[N]; const int K = 20; int p[N]; int pskip[K][N]; int dep[N]; int euler_tour[2 * N]; int tour_sz; int first_time_on_tour[N]; int last_time_on_tour[N]; int lg2[2 * N]; int idup[N]; //vector<int> g[N]; pair<int, int> tab_lca[2 * N][K]; void dfs_lca(int a, int par = 0) { p[a] = par; euler_tour[++tour_sz] = a; first_time_on_tour[a] = last_time_on_tour[a] = tour_sz; for (auto &it : gg[a]) { int b=it.first; int i=it.second; if (b==par){ continue; } idup[b]=i; dep[b] = 1 + dep[a]; dfs_lca(b, a); euler_tour[++tour_sz] = a; last_time_on_tour[a] = tour_sz; } } void lcaTM() { dfs_lca(1); for (int i = 2; i <= tour_sz; i++) { lg2[i] = 1 + lg2[i / 2]; } for (int i = 1; i <= tour_sz; i++) { tab_lca[i][0] = {dep[euler_tour[i]], euler_tour[i]}; } for (int k = 1; (1 << k) <= tour_sz; k++) { for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++) { tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]); } } } int lca(int a, int b) { if (first_time_on_tour[a] > last_time_on_tour[b]) { swap(a, b); } a = first_time_on_tour[a]; b = last_time_on_tour[b]; int k = lg2[b - a + 1]; return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second; } int goup(int a,int cnt){ assert(cnt>=0); for(int i=0;i<K;i++){ if(cnt&(1<<i)){ a=pskip[i][a]; } } return a; } int sol[N]; int tp[N]; int inc[N]; int dcr[N]; void dfs2(int a){ inc[a]=max(inc[a],1); dcr[a]=max(dcr[a],1); for (auto &it:gg[a]){ int b=it.first; if(b==p[a]){ continue; } if(idup[a]<idup[b]){ inc[b]=1+inc[a]; }else{ dcr[b]=1+dcr[a]; } dfs2(b); } ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); /// freopen("___input___.txt","r",stdin); cin>>n>>k; for(int i=1;i<=n+k-1;i++){ string s; cin>>s; assert(s=="S"||s=="Q"||s=="C"); if(s=="S"){ int a,b; cin>>a>>b; ///g[a].push_back(b); ///g[b].push_back(a); gg[a].push_back({b, i}); gg[b].push_back({a, i}); sol[i]=-1; } if(s=="Q"){ int a,b; cin>>a>>b; if(a==b){ tp[i]=1; sol[i]=1; }else{ q2[a].push_back({b, i}); tp[i]=1; sol[i]=-2; } } if(s=="C"){ int a; cin>>a; q1[a].push_back(i); sol[i]=-3; } } lcaTM(); dfs2(1); /// solve q1 for the general case for (int i=1;i<=n;i++){ pskip[0][i]=p[i]; } for (int k=1;k<K;k++){ for (int i=1;i<=n;i++){ pskip[k][i]=pskip[k-1][pskip[k-1][i]]; } } for (int a=1;a<=n;a++){ for (auto &it:q2[a]){ int b=it.first,i=it.second; /** **/ /// drumul de la b la a e crescator? vector<int> guys_x,guys_y; int x=a,y=b,z; swap(x,y); z=lca(x,y); int last=-1; if(y!=z){ last=idup[y]; }else{ // cout<<"ici\n"; assert(x!=z); assert(dep[x]-dep[z]-1>=0); // cout<<x << " : "<<dep[x]-dep[z]-1<<"\n"; int vlx=goup(x,dep[x]-dep[z]-1); assert(p[vlx]==z); last=idup[vlx]; } bool ok2=1,ok2y=(inc[y]>=dep[y]-dep[z]); ok2&=(dcr[x]>=dep[x]-dep[z]); ///ok2&=(dcr[y]>=dep[z]-dep[y]); /// cout<<" : "<<okx<<" vs "<<inc[x]<<" "<<dep[x]-dep[z]+1<<"\n"; int xx=x; while (x!=z){ guys_x.push_back(idup[x]); x=p[x]; } while(y!=z){ guys_y.push_back(idup[y]); y=p[y]; } bool okx=1,oky=1; for (int it=1;it<(int)guys_x.size();it++) { okx&=(guys_x[it-1]<guys_x[it]); } /// cout<<okx<<" : "<<dcr[xx]<<" vs "<<dep[xx]-dep[z]<<"\n"; assert(okx==ok2); for (int it=1;it<(int)guys_y.size();it++) { oky&=(guys_y[it-1]>guys_y[it]); } assert(ok2y==oky); vector<int> guys=guys_x; reverse(guys_y.begin(),guys_y.end()); for (auto &V:guys_y){ guys.push_back(V); } bool ok=1; /* cout<< " ---> "; for (auto &it : guys){ cout<<it<<" "; } cout<<"\n";*/ assert(!guys.empty()); assert(guys.back()==last); for (int it=1;it<(int)guys.size();it++){ ok&=(guys[it-1]<guys[it]); } bool ok3=okx&oky; if(!guys_x.empty()&&!guys_y.empty()){ /// guys_x, guys_y ok3&=(guys_x.back()<=guys_y[0]); } assert(ok3==ok); /// cout<<" : " <<ok<<" "<<ok2<<"\n"; ///assert(ok==ok2); ok&=(guys.back()<i); sol[i]=ok; } } for (int i=1;i<=n+k-1;i++){ if(tp[i]==1){ assert(sol[i]==0||sol[i]==1); if(sol[i]==1){ cout<<"yes\n"; }else{ cout<<"no\n"; } } } return 0; }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:190:28: warning: unused variable 'xx' [-Wunused-variable]
  190 |                        int xx=x;
      |                            ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...