| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111712 | epicci23 | 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 "bits/stdc++.h"
#include "werewolf.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int INF = 1000000007;
const int N = 400005;
const int LOG = 20;
struct DSU{
vector<int> par,siz,mini;
DSU(int _n){
par.resize(_n+5);
iota(all(par),0);
siz.assign(_n+5,1);
mini.resize(_n+5);
iota(all(mini),0);
}
int find(int a){
if(par[a]==a) return a;
return par[a]=find(par[a]);
}
void unite(int a,int b){
a=find(a),b=find(b);
if(a==b) return;
if(siz[a]>siz[b]) swap(a,b);
par[a]=b;
siz[b]+=siz[a];
}
};
vector<int> v[N],human[N],wolf[N];
vector<int> hin(N,INF),hout(N,-INF),win(N,INF),wout(N,-INF);
int wift[N][LOG],hift[N][LOG],Tman[N],Twolf[N],hp,wp,ptr;
void hfs(int c){
if(sz(human[c])){
hout[c]=hin[c]=++ptr;
return;
}
for(int i=1;i<LOG;i++) hift[c][i]=hift[hift[c][i-1]][i-1];
for(int x:human[c]){
hift[x][0]=c;
hfs(x);
hin[c]=min(hin[c],hin[x]);
hout[c]=max(hout[c],hout[x]);
}
}
void wfs(int c){
if(sz(wolf[c])){
wout[c]=win[c]=++ptr;
return;
}
for(int i=1;i<LOG;i++) wift[c][i]=wift[wift[c][i-1]][i-1];
for(int x:wolf[c]){
wift[x][0]=c;
wfs(x);
win[c]=min(win[c],win[x]);
wout[c]=max(wout[c],wout[x]);
}
}
struct SegT{
vector<vector<int>> seg;
SegT(int _n){
seg.resize(4*_n+5);
}
void add(int rt,int l,int r,int ind,int u){
if(r<ind || l>ind) return;
if(l==r){
seg[rt].push_back(u);
return;
}
int m=(l+r)/2;
add(rt*2,l,m,ind,u),add(rt*2+1,m+1,r,ind,u);
seg[rt].push_back(u);
}
int query(int rt,int l,int r,int gl,int gr,int bl,int br){
if(r<gl || l>gr) return 0;
if(l>=gl && r<=gr){
int it = lower_bound(all(seg[rt]),bl) - seg[rt].begin();
if(it<sz(seg[rt]) && seg[rt][it]<=br) return 1;
return 0;
}
int m=(l+r)/2;
return query(rt*2,l,m,gl,gr,bl,br) + query(rt*2+1,m+1,r,gl,gr,bl,br);
}
};
vector<int> check_validity(int _N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int n=_N,m=sz(X),q=sz(L);
for(int i=0;i<m;i++){
int a=X[i],b=Y[i];
v[a].push_back(b);
v[b].push_back(a);
}
hp=n;
DSU dsu(N),dsu2(N);
for(int i=n-1;i>=0;i--){
for(int x:v[i]){
if(x>i){
int A = dsu.find(i), B = dsu.find(x);
if(A==B) continue;
int parA = dsu.mini[dsu.find(i)], parB = dsu.mini[dsu.find(x)];
dsu.merge(A,B);
human[hp].push_back(parA);
human[hp].push_back(parB);
Tman[hp]=i;
dsu.mini[dsu.find(A)]=hp++;
}
}
}
wp=n;
for(int i=0;i<n;i++){
for(int x:v[i]){
if(x<i){
int A = dsu2.find(i), B = dsu2.find(x);
if(A==B) continue;
int parA = dsu2.mini[dsu2.find(i)], parB = dsu2.mini[dsu2.find(x)];
dsu2.merge(A,B);
wolf[wp].push_back(parA);
wolf[wp].push_back(parB);
Twolf[wp]=i;
dsu2.mini[dsu2.find(A)]=wp++;
}
}
}
for(int i=0;i<LOG;i++) wift[wp][i]=wp,hift[hp][i]=hp;
ptr=0;
hfs(hp);
ptr=0;
wfs(wp);
SegT T(N);
for(int i=0;i<n;i++) T.add(1,1,n,hin[i],win[i]);
for(int i=0;i<sz(T.seg);i++) sort(all(T.seg[i]));
vector<int> res(q,0);
for(int i=0;i<q;i++){
int st = S[i], fn = E[i];
for(int j=LOG-1;j>=0;j--){
if(Tman[hift[st][j]] < L[i]) continue;
st = hift[st][j];
}
for(int j=LOG-1;j>=0;j--){
if(Twolf[wift[fn][j]] > R[i]) continue;
fn = wift[fn][j];
}
if(T.query(1,1,n,hin[st],hout[st],win[fn],wout[fn])) res[i]=1;
else res[i]=0;
}
return res;
}