Submission #846843

#TimeUsernameProblemLanguageResultExecution timeMemory
846843Ahmed57Inside information (BOI21_servers)C++17
7.50 / 100
240 ms79696 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int,int>> adj[120001]; array<int,3>P[120001][18][2]; int hi[120001],stt[120001],enn[120001],tim = 0; void dfs(int x,int p,int co) { hi[x] = hi[p]+1; P[x][0][0]={p,co,co}; P[x][0][1]={p,co,co}; for(int i = 1;i<=17;i++){ P[x][i][0] = P[x][i-1][0]; auto[pr,last,ma]=P[x][i][0]; if(last<=P[pr][0][0][1]) { P[x][i][0]=P[pr][i-1][0]; P[x][i][0][2]=max(P[x][i][0][2],ma); } } for(int i = 1;i<=17;i++){ P[x][i][1] = P[x][i-1][1]; auto[pr,last,ma]=P[x][i][1]; if(last>=P[pr][0][1][1]) { P[x][i][1]=P[pr][i-1][1]; P[x][i][1][2]=max(P[x][i][1][2],ma); } } stt[x] = tim++; for(auto j:adj[x]){ if(j.first==p)continue; dfs(j.first,x,j.second); } enn[x] = tim; } bool ispr(int l, int b) { return(stt[l]<=stt[b]&&enn[b]<=enn[l]); } bool lca(int a,int b,int t) { int ss = 1 , vv = 0; if(ispr(P[a][17][ss][0],a)&&ispr(P[a][17][ss][0],b)&&ispr(P[b][17][vv][0],a)&&ispr(P[b][17][vv][0],b)){ }else{ return 0; } if(hi[a]<hi[b]){swap(a,b);swap(ss,vv);} int ma = -1; for(int i = 17;i>=0;i--){ if(hi[a]-(1<<i)>=hi[b]){ ma = max(ma,P[a][i][ss][2]); a = P[a][i][ss][0]; } } if(hi[a]!=hi[b])return 0; if(a==b)return (ma<t); for(int i = 17;i>=0;i--){ if(P[a][i][ss][0]!=P[b][i][vv][0]){ ma = max({ma,P[a][i][ss][2],P[b][i][vv][2]}); a = P[a][i][ss][0]; b = P[b][i][vv][0]; } } if(P[a][0][ss][0]!=P[b][0][vv][0]||hi[a]!=hi[b])return 0; return (max({ma,P[a][0][ss][2],P[b][0][vv][2]})<t)&&(P[a][0][ss][2]>P[b][0][vv][2]); } int main() { int n,q; cin>>n>>q; q+=n-1; pair<char,vector<int>> v[q]; for(int i = 0;i<q;i++) { cin >> v[i].first; if(v[i].first=='S') { int a,b; cin>>a>>b; adj[a].push_back({b,i}); adj[b].push_back({a,i}); }else if(v[i].first=='Q') { int a,b; cin>>a>> b; v[i].second={a,b}; }else{ int a; cin>>a; } } dfs(1,1,0); for(int i=0;i<q;i++) { if(v[i].first=='S'||v[i].first=='C')continue; int a= v[i].second[0],b=v[i].second[1]; if(lca(a,b,i)){ cout<<"yes\n"; }else{ cout<<"no\n"; } } return 0; }
#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...