Submission #336572

#	Time	Username	Problem	Language	Result	Execution time	Memory
336572		dlalswp25	Werewolf (IOI18_werewolf)	C++14	100 / 100	1254 ms	200064 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

int N, M, Q;
vector<int> ans;
vector<int> adj[202020];
vector<int> tre[404040];

vector<int> qv[202020];

int st[20][404040];
int mx[20][404040];
int lft[404040];
int rgt[404040];
int pos[202020];
int id;

struct DSU {
	set<int> V[202020];
	int sz[404040];
	int p[404040];

	void init(int n, bool isV) {
		for(int i = 0; i < n; i++) {
			p[i] = i;
			if(isV) {
				sz[i] = 1;
				V[i].insert(pos[i]);
			}
		}
	}

	int par(int x) {
		if(x == p[x]) return x;
		return p[x] = par(p[x]);
	}

	bool unite(int a, int b, bool isV) {
		a = par(a); b = par(b);
		if(a == b) return false;
		if(isV) {
			if(sz[a] < sz[b]) return unite(b, a, isV);
			sz[a] += sz[b];
			if(isV) for(int i : V[b]) V[a].insert(i);
			p[b] = a;
		}
		else p[b] = a;
		return true;
	}
}uf;

void dfs(int v, int p) {
	st[0][v] = p;
	mx[0][v] = max(v, p);
	if(!p) mx[0][v] = 1010101010;
	if(v < N) {
		lft[v] = rgt[v] = id;
		pos[v] = id;
		id++;
		return;
	}
	lft[v] = 2 * N; rgt[v] = -1;
	for(int i : tre[v]) {
		if(i == p) continue;
		dfs(i, v);
		lft[v] = min(lft[v], lft[i]);
		rgt[v] = max(rgt[v], rgt[i]);
	}
}

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();
	Q = S.size();
	ans.resize(Q);

	for(int i = 0; i < M; i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	uf.init(2 * N, false);
	for(int i = 0; i < N; i++) {
		tre[N + i].push_back(i);
		uf.unite(N + i, i, false);
		for(int j : adj[i]) {
			if(j > i) continue;
			int tmp = uf.par(j);
			if(uf.unite(i, j, false)) tre[N + i].push_back(tmp);
		}
	}

	// for(int i = 0; i < 2 * N; i++) {
	// 	printf("%d: ", i);
	// 	for(int j : tre[i]) printf("%d ", j); puts("");
	// }

	dfs(2 * N - 1, 0);
	for(int i = 1; i <= 19; i++) {
		for(int j = 0; j < 2 * N; j++) {
			st[i][j] = st[i - 1][st[i - 1][j]];
			mx[i][j] = max(mx[i - 1][j], mx[i - 1][st[i - 1][j]]);
		}
	}

	// for(int i = 0; i < N; i++) printf("%d ", pos[i]); puts("");

	for(int i = 0; i < Q; i++) {
		qv[L[i]].push_back(i);
	}

	uf.init(N, true);
	for(int i = N - 1; i >= 0; i--) {
		for(int j : adj[i]) {
			if(j < i) continue;
			uf.unite(i, j, true);
		}
		for(int j : qv[i]) {
			int u = E[j];
			for(int k = 19; k >= 0; k--) {
				if(mx[k][u] > N + R[j]) continue;
				u = st[k][u];
			}
			// lft[u], rgt[u];
			int s = uf.par(S[j]);
			auto it = uf.V[s].lower_bound(lft[u]);
			if(it != uf.V[s].end() && *it <= rgt[u]) ans[j] = 1;
		}
	}

	return ans;
}

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