oj.uz

Submission #336572

# Submission time Handle Problem Language Result Execution time Memory
336572 2020-12-15T18:53:52 Z dlalswp25 Werewolf (IOI18_werewolf) C++14
100 / 100
 1254 ms 200064 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29164 KB Output is correct
2 Correct 18 ms 29164 KB Output is correct
3 Correct 18 ms 29184 KB Output is correct
4 Correct 19 ms 29164 KB Output is correct
5 Correct 18 ms 29164 KB Output is correct
6 Correct 18 ms 29164 KB Output is correct
7 Correct 18 ms 29164 KB Output is correct
8 Correct 17 ms 29148 KB Output is correct
9 Correct 18 ms 29236 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29164 KB Output is correct
2 Correct 18 ms 29164 KB Output is correct
3 Correct 18 ms 29184 KB Output is correct
4 Correct 19 ms 29164 KB Output is correct
5 Correct 18 ms 29164 KB Output is correct
6 Correct 18 ms 29164 KB Output is correct
7 Correct 18 ms 29164 KB Output is correct
8 Correct 17 ms 29148 KB Output is correct
9 Correct 18 ms 29236 KB Output is correct
10 Correct 25 ms 31084 KB Output is correct
11 Correct 25 ms 31212 KB Output is correct
12 Correct 25 ms 31340 KB Output is correct
13 Correct 27 ms 31340 KB Output is correct
14 Correct 26 ms 31596 KB Output is correct
15 Correct 26 ms 31212 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 198252 KB Output is correct
2 Correct 1043 ms 169452 KB Output is correct
3 Correct 1067 ms 176620 KB Output is correct
4 Correct 1070 ms 190188 KB Output is correct
5 Correct 1049 ms 193284 KB Output is correct
6 Correct 1045 ms 197556 KB Output is correct
7 Correct 996 ms 200064 KB Output is correct
8 Correct 973 ms 169372 KB Output is correct
9 Correct 813 ms 174696 KB Output is correct
10 Correct 749 ms 190956 KB Output is correct
11 Correct 817 ms 192364 KB Output is correct
12 Correct 849 ms 196844 KB Output is correct
13 Correct 945 ms 164204 KB Output is correct
14 Correct 938 ms 164432 KB Output is correct
15 Correct 955 ms 164432 KB Output is correct
16 Correct 956 ms 164252 KB Output is correct
17 Correct 1000 ms 197912 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29164 KB Output is correct
2 Correct 18 ms 29164 KB Output is correct
3 Correct 18 ms 29184 KB Output is correct
4 Correct 19 ms 29164 KB Output is correct
5 Correct 18 ms 29164 KB Output is correct
6 Correct 18 ms 29164 KB Output is correct
7 Correct 18 ms 29164 KB Output is correct
8 Correct 17 ms 29148 KB Output is correct
9 Correct 18 ms 29236 KB Output is correct
10 Correct 25 ms 31084 KB Output is correct
11 Correct 25 ms 31212 KB Output is correct
12 Correct 25 ms 31340 KB Output is correct
13 Correct 27 ms 31340 KB Output is correct
14 Correct 26 ms 31596 KB Output is correct
15 Correct 26 ms 31212 KB Output is correct
16 Correct 994 ms 198252 KB Output is correct
17 Correct 1043 ms 169452 KB Output is correct
18 Correct 1067 ms 176620 KB Output is correct
19 Correct 1070 ms 190188 KB Output is correct
20 Correct 1049 ms 193284 KB Output is correct
21 Correct 1045 ms 197556 KB Output is correct
22 Correct 996 ms 200064 KB Output is correct
23 Correct 973 ms 169372 KB Output is correct
24 Correct 813 ms 174696 KB Output is correct
25 Correct 749 ms 190956 KB Output is correct
26 Correct 817 ms 192364 KB Output is correct
27 Correct 849 ms 196844 KB Output is correct
28 Correct 945 ms 164204 KB Output is correct
29 Correct 938 ms 164432 KB Output is correct
30 Correct 955 ms 164432 KB Output is correct
31 Correct 956 ms 164252 KB Output is correct
32 Correct 1000 ms 197912 KB Output is correct
33 Correct 1060 ms 170656 KB Output is correct
34 Correct 366 ms 62444 KB Output is correct
35 Correct 1182 ms 164892 KB Output is correct
36 Correct 1008 ms 171788 KB Output is correct
37 Correct 1118 ms 164972 KB Output is correct
38 Correct 1042 ms 170120 KB Output is correct
39 Correct 1158 ms 191824 KB Output is correct
40 Correct 1096 ms 171628 KB Output is correct
41 Correct 942 ms 165120 KB Output is correct
42 Correct 820 ms 170192 KB Output is correct
43 Correct 1254 ms 168524 KB Output is correct
44 Correct 1050 ms 164848 KB Output is correct
45 Correct 1084 ms 181856 KB Output is correct
46 Correct 1197 ms 191056 KB Output is correct
47 Correct 999 ms 164388 KB Output is correct
48 Correct 964 ms 164408 KB Output is correct
49 Correct 985 ms 164324 KB Output is correct
50 Correct 969 ms 164520 KB Output is correct
51 Correct 1050 ms 170632 KB Output is correct
52 Correct 1024 ms 170740 KB Output is correct