| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 768757 | Baytoro | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#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;
}
}