Submission #733784

#TimeUsernameProblemLanguageResultExecution timeMemory
733784nekiWerewolf (IOI18_werewolf)C++14
0 / 100
647 ms96764 KiB
#include <bits/stdc++.h> #include "werewolf.h" #define vc vector using namespace std; vc<int> check_validity(int n, vc<int> a, vc<int> b, vc<int> S, vc<int> E, vc<int> ql, vc<int> qr){ int m=a.size(), Q=S.size(); for(int i=0;i<m;++i)if(a[i]>b[i])swap(a[i],b[i]); vc<vc<int>> ledg(n), redg(n);for(int i=0;i<m;++i)ledg[b[i]].push_back(a[i]),redg[a[i]].push_back(b[i]); vc<vc<int>> lqs(n), rqs(n);for(int i=0;i<Q;++i)lqs[qr[i]].push_back(i),rqs[ql[i]].push_back(i); vc<int> ldsu(n),rdsu(n);for(int i=0;i<n;++i)ldsu[i]=i,rdsu[i]=i; function<int(int,vc<int>&)> fnd=[&fnd](int u,vc<int>& dsu){return (u==dsu[u])?u:dsu[u]=fnd(dsu[u],dsu);}; vc<vc<int>> ltr(n),rtr(n); vc<int> lranno(Q),rranno(Q); for(int u=0;u<n;++u){ for(auto v:ledg[u]){int pv=fnd(v,ldsu);if(pv!=u)ldsu[pv]=u,ltr[u].push_back(pv);} for(auto q:lqs[u])lranno[q]=fnd(E[q],ldsu); } for(int u=n-1;u>=0;--u){ for(auto v:redg[u]){int pv=fnd(v,rdsu);if(pv!=u)rdsu[pv]=u,rtr[u].push_back(pv);} for(auto q:rqs[u])rranno[q]=fnd(S[q],rdsu); } function<void(int,int&,vc<vc<int>>&,vc<int>&,vc<int>&)> eul=[&eul](int u,int& T,vc<vc<int>>& tr,vc<int>& lran,vc<int>& rran){ lran[u]=T++; for(auto v:tr[u])eul(v,T,tr,lran,rran); rran[u]=T; }; int lT=0,rT=0; vc<int> lranx(n),rranx(n),lrany(n),rrany(n); for(int u=0;u<n;++u)if(u==ldsu[u])eul(u,lT,ltr,lranx,rranx); for(int u=n-1;u>=0;--u)if(u==rdsu[u])eul(u,rT,rtr,lrany,rrany); assert(lT==n&&rT==n); vc<array<int,3>> sw; for(int i=0;i<n;++i)sw.emplace_back(array<int,3>{lranx[i],0,lrany[i]}); for(int i=0;i<Q;++i)sw.emplace_back(array<int,3>{lranx[lranno[i]],1,i}); sort(sw.begin(),sw.end()); vc<int> ans(Q,0); vc<vc<int>> sgtr(2*n); for(auto q:sw){ if(q[1]==0){ for(int y=q[2]+n;y>0;y>>=1){ while(sgtr[y].size()){int i=sgtr[y].back();sgtr[y].pop_back();if(q[0]<rranx[lranno[i]])ans[i]=1;} } } if(q[1]==1){ int i=q[2]; for(int l=lrany[rranno[i]]+n, r=rrany[rranno[i]]+n;l<r;l>>=1,r>>=1){ if(l&1)sgtr[l++].push_back(i); if(r&1)sgtr[--r].push_back(i); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...