제출 #581991

#제출 시각아이디문제언어결과실행 시간메모리
581991WongChun1234Inside information (BOI21_servers)C++14
50 / 100
3261 ms353620 KiB
#include<bits/stdc++.h> using namespace std; const int N=120050; const int Q=240050; const bool DEBUG=0; int n,k,sz[N],u[Q],v[Q],t[N],preord[N],postord[N],pt; char ty[Q]; bool del[N]; map<int,int> tonde[N],frmnde[N],incen[N]; vector<int> adj[N]; void mainprec(int nde,int par){ preord[nde]=++pt; for (int i:adj[nde]) if (i!=par) mainprec(i,nde); postord[nde]=pt; } bool isa(int a,int b){ return (preord[a]<=preord[b]&&postord[a]>=postord[b]); } int qedge(int a,int b){ return (isa(a,b)?t[b]:t[a]); } void prec(int nde,int par){ sz[nde]=1; for (int i:adj[nde]){ if (del[i]) continue; if (i==par) continue; prec(i,nde); sz[nde]+=sz[i]; } } int findcen(int nde,int par,int mx){ for (int i:adj[nde]){ if (del[i]) continue; if (i==par) continue; if (sz[i]>mx/2) return findcen(i,nde,mx); } return nde; } void comp(int nde,int par,int smallrt,int bigrt,int mindist,int mxdist){ if (DEBUG) cerr<<nde<<":"<<par<<" "<<smallrt<<","<<bigrt<<"::"<<mindist<<","<<mxdist<<"\n"; incen[nde][bigrt]=smallrt; tonde[bigrt][nde]=mxdist; frmnde[bigrt][nde]=mindist; for (int i:adj[nde]){ if (del[i]) continue; if (i==par) continue; if (qedge(nde,i)>mxdist){ comp(i,nde,smallrt,bigrt,INT_MIN,qedge(nde,i)); }else if (qedge(nde,i)<mindist){ comp(i,nde,smallrt,bigrt,qedge(nde,i),INT_MAX); }else{ comp(i,nde,smallrt,bigrt,INT_MIN,INT_MAX); } } } void dc(int nde){ prec(nde,nde); int cen=findcen(nde,nde,sz[nde]); if (DEBUG) cerr<<nde<<":"<<cen<<"uwuuwu\n"; del[cen]=1; for (int i:adj[cen]){ if (del[i]) continue; comp(i,cen,i,cen,qedge(cen,i),qedge(cen,i)); } for (int i:adj[cen]){ if (del[i]) continue; dc(i); } } bool check(int rt,int v,int u,int id){ // v->u if (u==rt){ if (frmnde[rt][v]==INT_MIN) return 0; return (qedge(rt,incen[v][rt])<=id); }else if (v==rt){ if (tonde[rt][u]==INT_MAX) return 0; return (tonde[rt][u]<=id); }else{ if (incen[u][rt]==incen[v][rt]) return 0; if (qedge(incen[v][rt],rt)>qedge(incen[u][rt],rt)) return 0; if (frmnde[rt][v]==INT_MIN) return 0; if (tonde[rt][u]>id) return 0; return 1; } } int main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>k; for (int i=1;i<n+k;i++){ cin>>ty[i]>>u[i]; if (ty[i]=='S'){ cin>>v[i]; adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); }else if (ty[i]=='Q'){ cin>>v[i]; }else{ //??? } } mainprec(1,1); for (int i=1;i<n+k;i++){ if (ty[i]!='S') continue; if (isa(u[i],v[i])) t[v[i]]=i; else t[u[i]]=i; } dc(1); for (int i=1;i<n+k;i++){ if (ty[i]=='Q'){ //check if v->u exists if (u[i]==v[i]){ cout<<"yes\n"; goto skip; } if (DEBUG) cerr<<v[i]<<",,"<<u[i]<<"\n"; for (auto j:incen[v[i]]){ if (!j.second) continue; if (DEBUG) cerr<<j.first<<"::"<<j.second<<"a\n"; if ((!!incen[u[i]][j.first])||j.first==u[i]){ if (DEBUG) cerr<<v[i]<<"->"<<incen[v[i]][j.first]<<"--"<<j.first<<"--"<<incen[u[i]][j.first]<<"->"<<u[i]<<"\n"; if (check(j.first,v[i],u[i],i)){ cout<<"yes\n"; goto skip; } } } if (incen[u[i]][v[i]]){ if (check(v[i],v[i],u[i],i)){ cout<<"yes\n"; goto skip; } } cout<<"no\n"; skip:; }else if (ty[i]=='C'){ cout<<"42\n"; } } }
#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...