Submission #768757

#TimeUsernameProblemLanguageResultExecution timeMemory
768757BaytoroWerewolf (IOI18_werewolf)C++17
Compilation error
0 ms0 KiB
//#include "werewolf.h" #include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define pb push_back const int N=2e5+5; vector<int> g[N]; int v[N],used[N],a[N]; void dfs(int x){ a[v[x]]=x; for(auto it: g[x]){ if(v[it]!=-1) continue; v[it]=v[x]+1; dfs(it); } } struct SparseTable{ int mn[N][21],mx[N][21]; void build(){ for(int i=0;i<N;i++) mn[i][0]=mx[i][0]=a[i]; for(int j=1;j<21;j++){ for(int i=0;i+(1<<j)-1<N;i++){ mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); } } } int minn(int l, int r){ int lg=__lg(r-l+1); return min(mn[l][lg],mn[r-(1<<lg)+1][lg]); } int maxx(int l, int r){ int lg=__lg(r-l+1); return max(mx[l][lg],mx[r-(1<<lg)+1][lg]); } } sparse; int col[N]; void dfs1(int x, int c, vector<int> &used){ used[x]=1; //cout<<x<<' '<<c<<' '<<col[x]<<endl; for(auto it: g[x]){ if(used[it]) continue; if(c==1 && col[it]<=1) dfs1(it,c,used); if(c==2 && col[it]>=1) dfs1(it,c,used); } } vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){ for(int i=0;i<N;i++) v[i]=-1; int m=X.size(),q=S.size(); //Subtask 3 for(int i=0;i<m;i++){ g[X[i]].pb(Y[i]); g[Y[i]].pb(X[i]); } if(n<=3000){ vector<int> ans(q); for(int i=0;i<q;i++){ if(E[i]>R[i] || S[i]<L[i]) continue; for(int j=0;j<n;j++){ if(j<L[i]) col[j]=2; else if(j<=R[i]) col[j]=1; else col[j]=0; } vector<int> a(n),b(n); dfs1(S[i],1,a); dfs1(E[i],2,b); for(int j=L[i];j<=R[i];j++) if(a[j] && b[j]) ans[i]=1; } return ans; } else{ for(int i=0;i<n;i++){ if(g[i].size()==1){ v[i]=0; dfs(i); break; } } sparse.build(); vector<int> ans(q); for(int i=0;i<q;i++){ int l=v[S[i]],r=v[E[i]]; if(l<r){ //cout<<1<<endl; int lx=l,rx=r; for(int j=(1<<20);j>0;j/=2){ if(lx+j<=r && sparse.minn(l,lx+j)>=L[i]) lx+=j; if(rx-j>=l && sparse.maxx(rx-j,r)<=R[i]) rx-=j; } if(rx<=lx) ans[i]=1; } if(r<l){ //cout<<2<<endl; int lx=r, rx=l; for(int j=(1<<20);j>0;j/=2){ if(lx+j<=l && sparse.maxx(r,lx+j)<=R[i]) lx+=j; if(rx-j>=r && sparse.minn(rx-j,l)>=L[i]) rx-=j; } if(rx<=lx) ans[i]=1; } } return ans; } }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc8NHHA2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEdba03.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status