Submission #553241

#	Time	Username	Problem	Language	Result	Execution time	Memory
553241		jamezzz	Werewolf (IOI18_werewolf)	C++17	100 / 100	906 ms	144460 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;

#define maxn 400005

int cnt,par[maxn];
void init(int N){
	for(int i=0;i<N;++i){
		par[i]=i;
	}
}
int fp(int i){
	return (par[i]==i)?i:par[i]=fp(par[i]);
}
int join(int x,int y){
	x=fp(x),y=fp(y);
	par[x]=par[y]=cnt;
	return cnt++;
}

vi AL1[maxn],AL2[maxn],ord1;
int dfscnt;
int p1[maxn][20],w1[maxn],r1[maxn],pre1[maxn],pst1[maxn];
int p2[maxn][20],w2[maxn],r2[maxn],pre2[maxn],pst2[maxn],pos[maxn];

void dfs1(int u){
	pre1[u]=dfscnt;
	if(AL1[u].size()==0){
		++dfscnt;
		ord1.pb(u);
	}
	for(int v:AL1[u]){
		p1[v][0]=u;
		dfs1(v);
	}
	pst1[u]=dfscnt-1;
}

void dfs2(int u){
	pre2[u]=dfscnt;
	if(AL2[u].size()==0){
		++dfscnt;
	}
	for(int v:AL2[u]){
		p2[v][0]=u;
		dfs2(v);
	}
	pst2[u]=dfscnt-1;
}

int n,v[2*maxn];
void up(int i,int s,int e,int x,int nv){
	if(s==x&&e==x){v[i]=nv;return;}
	int m=(s+e)>>1;
	if(x<=m)up(2*i+1,s,m,x,nv);
	else up(2*i+2,m+1,e,x,nv);
	v[i]=max(v[2*i+1],v[2*i+2]);
}
void up(int x,int nv){
	up(0,0,n-1,x,nv);
}
int qry(int i,int s,int e,int x,int y){
	if(s==x&&e==y)return v[i];
	int m=(s+e)>>1;
	if(y<=m)return qry(2*i+1,s,m,x,y);
	if(x>m)return qry(2*i+2,m+1,e,x,y);
	return max(qry(2*i+1,s,m,x,m),qry(2*i+2,m+1,e,m+1,y));
}
int qry(int x,int y){
	return qry(0,0,n-1,x,y);
}

struct query{
	int l1,r1,l2,r2,i;
};
vector<query> qrys;

vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
	int Q=S.size(),M=X.size();
	
	vector<ii> edges;
	for(int i=0;i<M;++i){
		edges.pb({X[i],Y[i]});
	}
	
	sort(all(edges),[](ii &a,ii &b){return min(a.fi,a.se)>min(b.fi,b.se);});
	init(2*N);cnt=N;
	for(ii pr:edges){
		int a=fp(pr.fi),b=fp(pr.se);
		if(a!=b){
			int p=join(a,b);
			w1[p]=min(pr.fi,pr.se);
			AL1[p].pb(a);
			AL1[p].pb(b);
		}
	}
	sort(all(edges),[](ii &a,ii &b){return max(a.fi,a.se)<max(b.fi,b.se);});
	init(2*N);cnt=N;
	for(ii pr:edges){
		int a=fp(pr.fi),b=fp(pr.se);
		if(a!=b){
			int p=join(a,b);
			w2[p]=max(pr.fi,pr.se);
			AL2[p].pb(a);
			AL2[p].pb(b);
		}
	}
	
	memset(p1,-1,sizeof p1);
	dfscnt=0;
	dfs1(cnt-1);
	memset(p2,-1,sizeof p2);
	dfscnt=0;
	dfs2(cnt-1);
	
	for(int k=1;k<20;++k){
		for(int i=0;i<cnt;++i){
			if(p1[i][k-1]!=-1)p1[i][k]=p1[p1[i][k-1]][k-1];
			if(p2[i][k-1]!=-1)p2[i][k]=p2[p2[i][k-1]][k-1];
		}
	}
	
	//pf("pre1: ");for(int i=0;i<N;++i)pf("%d ",pre1[i]);pf("\n");
	//pf("pre2: ");for(int i=0;i<N;++i)pf("%d ",pre2[i]);pf("\n");
	//pf("w1: ");for(int i=0;i<cnt;++i)pf("%d ",w1[i]);pf("\n");
	//pf("w2: ");for(int i=0;i<cnt;++i)pf("%d ",w2[i]);pf("\n");
	
	for(int i=0;i<Q;++i){
		query q={0,0,0,0,i};
		//pf("qry: %d %d %d %d\n",S[i],E[i],L[i],R[i]);
		int cur=S[i];
		for(int k=19;k>=0;--k){
			if(p1[cur][k]!=-1&&w1[p1[cur][k]]>=L[i])cur=p1[cur][k];
		}
		q.l1=pre1[cur];
		q.r1=pst1[cur];
		
		cur=E[i];
		for(int k=19;k>=0;--k){
			if(p2[cur][k]!=-1&&w2[p2[cur][k]]<=R[i])cur=p2[cur][k];
		}
		q.l2=pre2[cur];
		q.r2=pst2[cur];
		//pf("%d %d %d %d\n",q.l1,q.r1,q.l2,q.r2);
		qrys.pb(q);
	}
	
	vi A(Q,0);
	sort(all(qrys),[](query &a,query &b){return a.r1<b.r1;});
	n=N;memset(v,-1,sizeof v);
	int pv=-1;
	for(int i=0;i<Q;++i){
		query &q=qrys[i];
		while(pv<q.r1){
			++pv;
			int x=ord1[pv];//node index
			int pos=pre2[x];//preorder
			up(pos,pv);
		}
		int val=qry(q.l2,q.r2);
		if(val>=q.l1)A[q.i]=1;
	}
	return A;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51