Submission #1085093

#TimeUsernameProblemLanguageResultExecution timeMemory
1085093ASN49KWerewolf (IOI18_werewolf)C++14
34 / 100
403 ms524288 KiB
#include "werewolf.h" #include <bits/stdc++.h> #define all(x) x.begin(),x.end() using namespace std; struct query { int x,y,val_l,val_r,lx,rx,ly,ry,ind; }; const int N=200'000,UNSET=-1; int poz[N]; namespace dsu { vector<int>t,l,r; void init(int n) { t.resize(n); l.resize(n); r.resize(n); iota(all(t) , 0); for(int i=0;i<n;i++) { l[i]=r[i]=poz[i]; } } int root(int x) { if(t[x]!=x) { t[x]=root(t[x]); } return t[x]; } void unite(int x,int y) { x=root(x); y=root(y); if(x!=y) { t[y]=x; l[x]=min(l[x],l[y]); r[x]=max(r[x],r[y]); } } } int acm=-1; int n,q; vector<int>adj[N]; vector<query>querys; bool intersect(int lx,int rx,int ly,int ry) { return max(lx,ly)<=min(rx,ry); } void dfs(int nod,int tt) { poz[nod]=++acm; for(auto &c:adj[nod]) { if(c!=tt) { dfs(c,nod); } } } std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) { n=N; q=(int)L.size(); vector<int>rez(q); for(int i=0;i<(int)X.size();i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } for(int i=0;i<n;i++) { if(adj[i].size()==1) { dfs(i,UNSET); break; } } querys.resize(q); for(int i=0;i<q;i++) { assert(S[i]>=L[i] && E[i]<=R[i]); querys[i]={S[i],E[i],L[i],R[i],UNSET,UNSET,UNSET,UNSET,i}; } dsu::init(n); sort(all(querys),[&](const query& a,const query& b){ return a.val_l>b.val_l; }); int last=n; for(auto &c:querys) { while(last>c.val_l) { last--; for(auto &v:adj[last]) { if(last<v) { dsu::unite(v,last); } } } c.lx=dsu::l[dsu::root(c.x)]; c.rx=dsu::r[dsu::root(c.x)]; } dsu::init(n); sort(all(querys),[&](const query& a,const query& b){ return a.val_r<b.val_r; }); last=-1; for(auto &c:querys) { while(last<c.val_r) { last++; for(auto &v:adj[last]) { if(v<last) { dsu::unite(v,last); } } } c.ly=dsu::l[dsu::root(c.y)]; c.ry=dsu::r[dsu::root(c.y)]; } for(auto &c:querys) { rez[c.ind]=intersect(c.lx,c.rx,c.ly,c.ry); if(c.x<c.val_l || c.y>c.val_r) { rez[c.ind]=false; } } return rez; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...