Submission #332475

#	Time	Username	Problem	Language	Result	Execution time	Memory
332475		pit4h	Werewolf (IOI18_werewolf)	C++14	15 / 100	1627 ms	524292 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;
};
struct Segtree {
	vector<int> updates, tree;
	int base = 1;
	Segtree(int _N) {
		while(base<_N) base*=2;
		tree.resize(2*base+1, 0);
	}
	void upd(int x) {
		updates.push_back(x);
		x += base;
		while(x) {
			tree[x]++;
			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;
	}
	void clr() {
		updates.clear();
		tree.clear();
	}
};
Segtree *occ[MAXN];
struct Form {
	vector<vector<int>> g, anc;
	vector<vector<Query>> queries;
	vector<int> pre, range;	
	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);
		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];
		for(int i: g[x]) {
			dfs(i, x);
			range[x] = max(range[x], range[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) {
		int big_child = -1;
		for(int i: g[x]) {
			solve(i, x);	
			if(big_child==-1 || occ[i]->updates.size() > occ[big_child]->updates.size()) {
				big_child = i;
			}
		}
		if(big_child==-1) {
			occ[x] = new Segtree(N);
		}
		else {
			occ[x] = occ[big_child];
		}
		for(int i: g[x]) {
			if(i!=big_child) {
				for(int j: occ[i]->updates) {
					occ[x]->upd(j);
				}
				occ[i]->clr();
			}
		}
		occ[x]->upd(other->pre[x]);
		for(auto q: queries[x]) {
			ans[q.id] = (occ[x]->qry(q.l, q.r) > 0);
		}
	}
};

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);

	return ans;
}

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