Submission #207956

#	Time	Username	Problem	Language	Result	Execution time	Memory
207956		red1108	Werewolf (IOI18_werewolf)	C++17	100 / 100	1644 ms	174076 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;

int n, m;
//1 이 N->1, 2가 1->N순서
vector<int> tree1[200010], tree2[200010], gr[200010];
pii rn1[200010], rn2[200010];
int mi[20][200010], ma[20][200010], par1[20][200010], par2[20][200010];
int anc[200010], ord;
int nh[200010], root[200010];
int findanc(int x){
	if(x==anc[x]) return x;
	return anc[x]=findanc(anc[x]);
}
void dfs1(int x, int par){
	//printf("dfs1(%d %d)\n", x, par);
	mi[0][x] = par;
	par1[0][x]=par;
	rn1[x].fi = ++ord;
	for(auto i:tree1[x]) if(i!=par){
		dfs1(i,x);
	}
	rn1[x].se = ord;
}
void dfs2(int x, int par){
	//printf("dfs2(%d %d)\n", x, par);
	ma[0][x] = par;
	par2[0][x]=par;
	rn2[x].fi = ++ord;
	nh[rn1[x].fi] = ord;
	for(auto i:tree2[x]) if(i!=par){
		dfs2(i,x);
	}
	rn2[x].se = ord;
}
struct Node{
	int sum, l, r;
	Node(){l=r=sum=0;}
};
vector<Node> pst;
void gang(int bef, int cur, int l, int r, int i){
	pst[cur] = pst[bef];
	pst[cur].sum++;
	if(l==r) return ;
	int m = (l+r)/2;
	if(i<=m){
		pst[cur].l = pst.size();
		pst.push_back(Node());
		gang(pst[bef].l, pst[cur].l, l, m, i);
	}
	else{
		pst[cur].r = pst.size();
		pst.push_back(Node());
		gang(pst[bef].r,pst[cur].r, m+1, r, i);
	}
}
int get(int bef, int cur, int l, int r, int s, int e){
	if(r<s||e<l||s>e) return 0;
	if(s<=l&&r<=e) return pst[cur].sum - pst[bef].sum;
	return get(pst[bef].l, pst[cur].l, l, (l+r)/2, s, e)
			+ get(pst[bef].r, pst[cur].r, (l+r)/2+1, r, s, e);
}
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;
	m = X.size();
	for(int i=0;i<m;i++){
		int a = X[i], b =  Y[i]; a++;b++;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	for(int i=1;i<=n;i++) anc[i]=i;
	for(int i=n;i>=1;i--){
		for(auto j:gr[i]){
			if(j<i) continue;
			int a = findanc(j), b = findanc(i);
			if(a==b) continue;
			anc[a]=b;
			tree1[a].push_back(b);
			tree1[b].push_back(a);
		}
	}
	for(int i=1;i<=n;i++) anc[i]=i;
	for(int i=1;i<=n;i++){
		for(auto j:gr[i]){
			if(j>i) continue;
			int a = findanc(j), b = findanc(i);
			if(a==b) continue;
			anc[a]=b;
			tree2[a].push_back(b);
			tree2[b].push_back(a);
		}
	}
	ord=0;dfs1(1, 0);
	ord=0;dfs2(n, 0);
	ma[0][n] = 2*n;
	//cout<<"phase1"<<endl;
	pst.push_back(Node());
	//for(int i=1;i<=n;i++) printf("nh[%d]=%d\n", i, nh[i]);
	for(int i=1;i<=n;i++){
		root[i]=pst.size();
		pst.push_back(Node());
		gang(root[i-1], root[i], 1, n, nh[i]);
	}
	//cout<<"phase2"<<endl;
	for(int i=1;i<20;i++){
		for(int j=1;j<=n;j++){
			par1[i][j] = par1[i-1][par1[i-1][j]];
			par2[i][j] = par2[i-1][par2[i-1][j]];
			mi[i][j] = min(mi[i-1][j], mi[i-1][par1[i-1][j]]);
			ma[i][j] = max(ma[i-1][j], ma[i-1][par2[i-1][j]]);
		}
	}
	//for(int i=1;i<=n;i++) printf("i=%d (%d %d)\n", i, rn1[i].fi, rn2[i].fi);
	int Q = S.size();
	std::vector<int> A(Q);
	for (int i = 0; i < Q; ++i) {
		S[i]++;E[i]++;L[i]++;R[i]++;
		int x = S[i], y = E[i];
		for(int j=19;j>=0;j--){
			if(mi[j][x]>=L[i]) x = par1[j][x];
			if(ma[j][y]<=R[i]) y = par2[j][y];
		}
		//printf("x = %d y = %d\n", x, y);
		int sum = get(root[rn1[x].fi-1], root[rn1[x].se], 1, n, rn2[y].fi, rn2[y].se);
		if(sum) A[i]=1;
		else A[i]=0;
	}
	return A;
}

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