Submission #1021561

#TimeUsernameProblemLanguageResultExecution timeMemory
1021561JakobZorzWerewolf (IOI18_werewolf)C++17
0 / 100
321 ms77360 KiB
#include"werewolf.h" #include<queue> #include<iostream> #include<set> #include<algorithm> using namespace std; int n,m,q; vector<int>nodes[200000]; struct RMQ{ vector<vector<int>>table; vector<int>lg2; int n; RMQ(vector<int>arr){ n=(int)arr.size(); table=vector<vector<int>>(20,vector<int>(n)); int curr=1; lg2=vector<int>(n+1); for(int i=2;i<=n;i++){ while((1<<curr)<=i) curr++; lg2[i]=curr-1; } table[0]=arr; for(int p=1;p<20;p++){ for(int i=0;i+(1<<p)<=n;i++){ table[p][i]=max(table[p-1][i],table[p-1][i+(1<<(p-1))]); } } } int get(int l,int r){ if(l==r) return 0; int lg=lg2[r-l]; return max(table[lg][l],table[lg][r-(1<<lg)]); } }; struct Query{ int S,E,L,R; int ans; }; bool cmp(Query*a,Query*b){ return a->L>b->L; } vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){ n=N; m=(int)X.size(); q=(int)S.size(); for(int i=0;i<n;i++){ nodes[i].clear(); } for(int i=0;i<m;i++){ nodes[X[i]].push_back(Y[i]); nodes[Y[i]].push_back(X[i]); } vector<int>line; { vector<int>comp(n); vector<vector<int>>comps(n); for(int i=0;i<n;i++){ set<int>to_add; int curr_comp=i; comp[i]=i; for(int ne:nodes[i]){ if(ne>i) continue; to_add.insert(comp[ne]); } for(int j:to_add){ if(comps[curr_comp].size()<comps[j].size()){ swap(curr_comp,j); } //cout<<"MERGING "<<comps[curr_comp].size()<<" <- "<<comps[j].size()<<endl; comps[curr_comp].push_back(i); comps[curr_comp].insert(comps[curr_comp].end(),comps[j].begin(),comps[j].end()); for(int k:comps[j]) comp[k]=curr_comp; } comps[curr_comp].push_back(i); } line=comps[comp[0]]; } vector<int>to_line(n); for(int i=0;i<(int)line.size();i++){ to_line[line[i]]=i; } RMQ rmq=RMQ(line); /*for(int i:line) cout<<i<<" "; cout<<"\n";*/ vector<Query*>qrs(q); for(int i=0;i<q;i++){ qrs[i]=new Query; qrs[i]->S=S[i]; qrs[i]->E=E[i]; qrs[i]->L=L[i]; qrs[i]->R=R[i]; qrs[i]->ans=0; } vector<Query*>srt=qrs; sort(srt.begin(),srt.end(),cmp); vector<int>comp(n); vector<vector<int>>comps(n); vector<set<int>>comps_line(n); //cout<<"ANSWERING QUERIES NOW"<<endl; int r=n-1; for(auto qry:srt){ while(r>=qry->L){ comp[r]=r; comps[r]={r}; comps_line[r].insert(to_line[r]); for(int ne:nodes[r]){ if(ne<r) continue; if(comp[ne]!=comp[r]){ int br=r; if(comps[comp[r]].size()<comps[comp[ne]].size()) swap(ne,r); comps[comp[r]].insert(comps[comp[r]].end(),comps[comp[ne]].begin(),comps[comp[ne]].end()); for(int i:comps_line[comp[ne]]) comps_line[comp[r]].insert(i); for(int i:comps[comp[r]]) comp[i]=comp[r]; r=br; } } r--; } int rl,rr; /*for(int j=0;j<(int)line.size();j++){ if(line[j]==qry->E){ //for(rr=j;rr<(int)line.size()&&line[rr]<=qry->R;rr++); //for(rl=j;rl>=0&&line[rl]<=qry->R;rl--); break; } }*/ { int i=to_line[qry->E]; int l=i,r=(int)line.size(); while(l<r-1){ int mid=(l+r)/2; if(rmq.get(i,mid+1)<=qry->R) l=mid; else r=mid; } rr=r; } { int i=to_line[qry->E]; int l=0,r=i; while(l<r-1){ int mid=(l+r)/2; if(rmq.get(mid,i)<=qry->R) r=mid; else l=mid; } rl=l; } auto iter=comps_line[comp[qry->S]].lower_bound(rl+1); if(iter!=comps_line[comp[qry->S]].end()&&*iter<rr) qry->ans=1; /*for(int i:comps_line[comp[qry->S]]){ if(rl<i&&i<rr) qry->ans=1; }*/ } vector<int>res(q); for(int i=0;i<q;i++) res[i]=qrs[i]->ans; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...