Submission #332551

#	Time	Username	Problem	Language	Result	Execution time	Memory
332551		pit4h	Werewolf (IOI18_werewolf)	C++14	100 / 100	1559 ms	117240 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+2, MAXM = 4e5+2, Log = 20;

vector<int> ans;
int Find(int x, vector<int>& f) {
	if(f[x] == x) return x;
	f[x] = Find(f[x], f);
	return f[x];
}
bool Union(int x, int y, vector<int>& f, vector<int>& cnt, vector<int>& mx, bool dir) {
	x = Find(x, f); y = Find(y, f);
	if(x==y) return false;
	if(cnt[x] < cnt[y]) swap(x, y);
	cnt[x] += cnt[y];
	cnt[y] = 0;
	f[y] = x;
	if(!dir) {
		mx[x] = max(mx[x], mx[y]);
	}
	else {
		mx[x] = min(mx[x], mx[y]);
	}
	return true;
}
struct Query {
	int l, r, id;
};
const int base = (1<<19);
int tree[2*base+1];
void ins(int x, int val) {
	x += base;
	while(x) {
		tree[x]+=val;
		x /= 2;
	}
}
int qry(int l, int r) {
	l+=base; r+=base;
	int res = tree[l]; if(l==r) return res;
	res += tree[r];
	while(l/2 != r/2) {
		if(l%2==0) res += tree[l+1];
		if(r%2==1) res += tree[r-1];
		l /= 2;
		r /= 2;
	}
	return res;
}
vector<int> *occ[MAXN];
struct Form {
	vector<vector<int>> g, anc;
	vector<vector<Query>> queries;
	vector<int> pre, range, subt;	
	int N, nr=0;
	Form *other;
	Form(int _N) {
		N = _N;
		g.resize(N); anc.resize(Log, vector<int>(N));
		pre.resize(N); range.resize(N); subt.resize(N);
		queries.resize(N);
	}
	void build_graph(vector<int>& X, vector<int>& Y, vector<int>& order) {
		int M = X.size();
		vector<int> f(N), cnt(N), mx(N); for(int i=0; i<N; ++i) f[i] = mx[i] = i, cnt[i]=1;
		vector<vector<int>> G(N);
		for(int i=0; i<M; ++i) {
			if( (X[i] < Y[i]) != (order[0] < order.back()) ) {
				swap(X[i], Y[i]);	
			}
			G[Y[i]].push_back(X[i]);
		}
		for(int i: order) {
			for(int j: G[i]) {
				int repj = mx[Find(j, f)];
				if(Union(i, j, f, cnt, mx, (order[0] > order.back()) )) {
					g[i].push_back(repj);
				}
			}
		}		
	}
	void build_anc() {
		for(int j=1; j<Log; ++j) {
			for(int i=0; i<N; ++i) {
				anc[j][i] = anc[j-1][anc[j-1][i]];
			}
		}
	}
	void dfs(int x, int par) {
		anc[0][x] = par;
		pre[x] = nr; nr++;
		range[x] = pre[x];
		subt[x] = 1;
		for(int i: g[x]) {
			dfs(i, x);
			range[x] = max(range[x], range[i]);
			subt[x] += subt[i];
		}		
		if(x==par) {
			build_anc();
		}
	}
	int lowest_ancestor(int x, int h) {
		for(int i=Log-1; i>=0; --i) {
			if(x==h) break;
			if(anc[i][x]==h || (x < h) == (anc[i][x] < h)) {
				x = anc[i][x];
			}
		}
		return x;
	}
	void solve(int x, int p, bool keep) {
		int big_child = -1;
		for(int i: g[x]) {
			if(big_child==-1 || subt[i] > subt[big_child]) {
				big_child = i;
			}
		}	
		for(int i: g[x]) {
			if(i!=big_child) {
				solve(i, x, 0);
			}
		}
		if(big_child==-1) {
			occ[x] = new vector<int>();
		}
		else {
			solve(big_child, x, 1);
			occ[x] = occ[big_child];
		}
		for(int i: g[x]) {
			if(i!=big_child) {
				for(int j: *occ[i]) {
					occ[x] -> push_back(j);
					ins(j, 1);
				}
			}
		}
		occ[x] -> push_back(other->pre[x]);
		ins(other->pre[x], 1);
		for(auto q: queries[x]) {
			ans[q.id] = (qry(q.l, q.r) > 0);
		}
		if(!keep) {
			for(int j: *occ[x]) {
				ins(j, -1);
			}
		}
	}
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	swap(S, E); // == swap(human, wolf)
	int Q = S.size();
	ans.resize(Q);

	vector<int> order;
	for(int i=0; i<N; ++i) order.push_back(i);

	Form human(N), wolf(N);
	wolf.other = &human;

	human.build_graph(X, Y, order);
	reverse(order.begin(), order.end());
	wolf.build_graph(X, Y, order);
	
	human.dfs(N-1, N-1);
	wolf.dfs(0, 0);
	
	for(int i=0; i<Q; ++i) {
		S[i] = human.lowest_ancestor(S[i], R[i]);
		E[i] = wolf.lowest_ancestor(E[i], L[i]);
		if(S[i] > R[i] || E[i] < L[i]) continue;
		wolf.queries[E[i]].push_back({human.pre[S[i]], human.range[S[i]], i});
	}
	wolf.solve(0, 0, 0);

	return ans;
}

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