Submission #1085069

#TimeUsernameProblemLanguageResultExecution timeMemory
1085069ASN49KWerewolf (IOI18_werewolf)C++14
0 / 100
120 ms28496 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; namespace dsu { vector<int>t,l,r; int init(int n) { t.resize(n); l.resize(n); r.resize(n); iota(all(t) , 0); iota(all(l) , 0); iota(all(r) , 0); } 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 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); } 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]); } querys.resize(q); for(int i=0;i<q;i++) { querys[i]={S[i],E[i],L[i],R[i],UNSET,UNSET,UNSET,UNSET,i}; } return rez; 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)]; } return rez; 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); } return rez; }

Compilation message (stderr)

werewolf.cpp: In function 'int dsu::init(int)':
werewolf.cpp:21:5: warning: no return statement in function returning non-void [-Wreturn-type]
   21 |     }
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...