oj.uz

Submission #295490

# Submission time Handle Problem Language Result Execution time Memory
295490 2020-09-09T17:25:01 Z mode149256 Split the Attractions (IOI19_split) C++14
40 / 100
 267 ms 50040 KB 
#include<bits/stdc++.h>
#include "split.h"
using namespace std;
#define x first
#define y second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vii = vector<vi>;
using pi = pair<int, int>;
using vpi = vector<pi>;

const int MX = 2e5 + 100;

int N, M;
int A, B, C;
vpi visos;
vii edges(MX);
vii zemyn(MX);
unordered_set<int> inTree[MX];
vi col(3);
vi kiek(3);
vi sz(MX, 0);
vi res;
vb been(MX, false);
vi par(MX);
vi szp(MX, 1);

int findSet(int i) { return (i == par[i] ? i : (par[i] = findSet(par[i]))); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
bool unionSet(int i, int j) {
	if (isSameSet(i, j)) return false;

	i = findSet(i);
	j = findSet(j);

	if (szp[i] > szp[j]) swap(i, j);

	par[i] = j;
	szp[j] += szp[i];
	return true;
}

bool colored = false;
bool nepilnas = false;

void makeSz(int x) {
	sz[x] = 1;
	been[x] = true;

	for (auto u : edges[x]) {
		if (been[u]) continue;
		inTree[x].insert(u);
		inTree[u].insert(x);
		// zemyn[x].emplace_back(u);

		makeSz(u);
		sz[x] += sz[u];
	}
}

void makeZemyn(int x) {
	been[x] = true;
	for (auto u : edges[x]) {
		if (been[u] or !inTree[x].count(u)) continue;
		zemyn[x].emplace_back(u);
		// printf("zemyn x -> u %d -> %d\n", x, u);
		makeZemyn(u);
	}
}

void color(int x, int p, int c) {
	if (kiek[c] <= 0) return;
	// printf("c = %d, x = %d, col = %d, kiek = %d\n", c, x, col[c], kiek[c]);
	res[x] = col[c];
	kiek[c]--;
	if (kiek[c] <= 0) return;

	for (auto u : edges[x])
		if (u != p and res[u] == 0)
			color(u, x, c);
}

void colorMult(int x, int c, int cent) {
	if (kiek[c] <= 0) return;
	res[x] = col[c];
	kiek[c]--;
	if (kiek[c] <= 0) return;

	for (auto u : edges[x]) {
		if (u == cent) continue;
		if (inTree[x].count(u) == 0) continue;
		if (res[u] != 0) continue;
		colorMult(u, c, cent);
	}
}

void colorZemyn(int x, int c) {
	if (kiek[c] <= 0) return;
	res[x] = col[c];
	kiek[c]--;
	if (kiek[c] <= 0) return;

	for (auto u : zemyn[x])
		colorZemyn(u, c);
}

void unite(int x) {
	for (auto u : zemyn[x]) {
		// printf("jungiu u = %d, x = %d\n", u, x);
		unionSet(x, u);
		unite(u);
	}
}

void colorAll(int x, int c) {
	been[x] = true;
	if (kiek[c] <= 0) return;
	// printf("c = %d, x = %d, col = %d, kiek = %d\n", c, x, col[c], kiek[c]);
	res[x] = col[c];
	kiek[c]--;
	if (kiek[c] <= 0) return;

	for (auto u : edges[x])
		if (!been[u])
			colorAll(u, c);
}

void solve(int x) {
	// x is centroid
	// been = vb(N, false);
	// makeSz(x);
	been = vb(N, false);
	makeZemyn(x);

	for (auto u : edges[x]) {
		if (inTree[x].count(u) == 0) continue;
		unite(u);
		// printf("x = %d, u = %d, szu = %d, szp = %d\n", x, u, sz[u], szp[findSet(u)]);
		assert(sz[u] == szp[findSet(u)]);

		if (sz[u] >= kiek[0]) {
#ifdef LOCAL
			printf("PIRMO x = %d, u = %d\n", x, u);
#endif
			colorZemyn(u, 0);
			color(x, u, 1);
			return;
		}
	}

	// reik jungt
	for (auto u : visos) {
		if (u.x == x or u.y == x) continue;
		if (isSameSet(u.x, u.y)) continue;

		inTree[u.x].insert(u.y);
		inTree[u.y].insert(u.x);

		unionSet(u.x, u.y);

		if (szp[findSet(u.x)] >= kiek[0]) {
#ifdef LOCAL
			printf("SUJUNGUS x = %d, u = %d %d\n", x, u.x, u.y);
#endif
			colorMult(findSet(u.x), 0, x);
			color(x, -1, 1);
			return;
		}
	}

	nepilnas = true;
}

void dfs(int x, int p) {
	int centroid = 1;
	for (auto u : edges[x]) {
		if (sz[u] > N / 2)
			centroid = 0;
	}

	if (centroid) {
		colored = true;
		solve(x);
		return;
	}

	for (auto u : edges[x]) {
		if (u == p or !inTree[x].count(u)) continue;

		int prevX = sz[x];
		int prevU = sz[u];

		sz[x] -= sz[u];
		sz[u] += sz[x];
		dfs(u, x);

		sz[x] = prevX;
		sz[u] = prevU;
		if (colored) return;
	}
}

void sortabc() {
	if (A >= B and A >= C) {
		col[2] = 1;
		kiek[2] = A;

		col[1] = 2;
		kiek[1] = B;

		col[0] = 3;
		kiek[0] = C;
	} else if (B >= A and B >= C) {
		col[2] = 2;
		kiek[2] = B;

		col[1] = 1;
		kiek[1] = A;

		col[0] = 3;
		kiek[0] = C;
	} else {
		col[2] = 3;
		kiek[2] = C;

		col[1] = 2;
		kiek[1] = B;

		col[0] = 1;
		kiek[0] = A;
	}

	if (kiek[0] > kiek[1]) {
		swap(kiek[0], kiek[1]);
		swap(col[0], col[1]);
	}
}

vi find_split(int n, int a, int b, int c, vi p, vi q) {
	res.resize(n, 0);
	N = n;
	A = a;
	B = b;
	C = c;
	M = (int)p.size();
	for (int i = 0; i < N; ++i)
		par[i] = i;
	for (int i = 0; i < M; ++i)
	{
		edges[p[i]].emplace_back(q[i]);
		edges[q[i]].emplace_back(p[i]);
	}

	sortabc();

	// if (kiek[0] == 1) {
	// 	been.resize(N, false);
	// 	colorAll(0, 1);
	// 	for (int i = 0; i < N; ++i)
	// 	{
	// 		if (!res[i]) {
	// 			if (kiek[0]) {
	// 				res[i] = col[0];
	// 				kiek[0]--;
	// 			} else {
	// 				res[i] = col[2];
	// 			}
	// 		}
	// 	}

	// 	return res;
	// }

	been.resize(N, false);
	makeSz(0);
	been.resize(N, false);
	dfs(0, -1);

	// for (int i = 0; i < N; ++i)
	// {
	// 	printf("%d ", res[i]);
	// }
	// printf("\n");
	// printf("col %d %d %d\n", col[0], col[1], col[2]);
	if (colored and !nepilnas) {
		for (int i = 0; i < N; ++i)
		{
			if (!res[i]) res[i] = col[2];
		}
	}
	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23040 KB ok, correct split
2 Correct 16 ms 23040 KB ok, correct split
3 Correct 16 ms 23040 KB ok, correct split
4 Correct 16 ms 23040 KB ok, correct split
5 Correct 16 ms 23040 KB ok, correct split
6 Correct 16 ms 23040 KB ok, correct split
7 Correct 240 ms 49656 KB ok, correct split
8 Correct 225 ms 46768 KB ok, correct split
9 Correct 226 ms 46072 KB ok, correct split
10 Correct 217 ms 50040 KB ok, correct split
11 Correct 227 ms 50040 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23040 KB ok, correct split
2 Correct 17 ms 23040 KB ok, correct split
3 Correct 16 ms 23040 KB ok, correct split
4 Correct 253 ms 47480 KB ok, correct split
5 Correct 204 ms 40572 KB ok, correct split
6 Correct 223 ms 50040 KB ok, correct split
7 Correct 224 ms 46456 KB ok, correct split
8 Correct 267 ms 43128 KB ok, correct split
9 Correct 198 ms 41592 KB ok, correct split
10 Correct 155 ms 40200 KB ok, correct split
11 Correct 155 ms 40184 KB ok, correct split
12 Correct 158 ms 40200 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23040 KB ok, correct split
2 Correct 205 ms 40552 KB ok, correct split
3 Correct 74 ms 30328 KB ok, correct split
4 Correct 17 ms 23040 KB ok, correct split
5 Correct 213 ms 44280 KB ok, correct split
6 Correct 210 ms 43768 KB ok, correct split
7 Correct 217 ms 44536 KB ok, correct split
8 Correct 225 ms 44920 KB ok, correct split
9 Correct 218 ms 44280 KB ok, correct split
10 Correct 65 ms 29176 KB ok, no valid answer
11 Correct 92 ms 31992 KB ok, no valid answer
12 Correct 188 ms 40196 KB ok, no valid answer
13 Correct 227 ms 40656 KB ok, no valid answer
14 Correct 166 ms 40200 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23040 KB ok, correct split
2 Correct 16 ms 23040 KB ok, no valid answer
3 Correct 16 ms 23040 KB ok, correct split
4 Correct 17 ms 23040 KB ok, correct split
5 Correct 17 ms 23040 KB ok, correct split
6 Correct 16 ms 23040 KB ok, correct split
7 Correct 17 ms 23168 KB ok, correct split
8 Correct 16 ms 23040 KB ok, correct split
9 Correct 20 ms 23552 KB ok, correct split
10 Correct 20 ms 23552 KB ok, correct split
11 Correct 18 ms 23040 KB ok, correct split
12 Correct 20 ms 23544 KB ok, correct split
13 Correct 16 ms 23040 KB ok, correct split
14 Correct 16 ms 23040 KB ok, correct split
15 Correct 17 ms 23040 KB ok, correct split
16 Correct 16 ms 23040 KB ok, correct split
17 Correct 16 ms 23040 KB ok, correct split
18 Correct 16 ms 23040 KB ok, correct split
19 Correct 18 ms 23168 KB ok, correct split
20 Correct 17 ms 23296 KB ok, correct split
21 Correct 20 ms 23552 KB ok, correct split
22 Correct 19 ms 23620 KB ok, correct split
23 Correct 19 ms 23680 KB ok, correct split
24 Correct 19 ms 23552 KB ok, correct split
25 Correct 19 ms 23680 KB ok, correct split
26 Incorrect 20 ms 23552 KB jury found a solution, contestant did not
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23040 KB ok, correct split
2 Correct 16 ms 23040 KB ok, correct split
3 Correct 16 ms 23040 KB ok, correct split
4 Correct 16 ms 23040 KB ok, correct split
5 Correct 16 ms 23040 KB ok, correct split
6 Correct 16 ms 23040 KB ok, correct split
7 Correct 240 ms 49656 KB ok, correct split
8 Correct 225 ms 46768 KB ok, correct split
9 Correct 226 ms 46072 KB ok, correct split
10 Correct 217 ms 50040 KB ok, correct split
11 Correct 227 ms 50040 KB ok, correct split
12 Correct 16 ms 23040 KB ok, correct split
13 Correct 17 ms 23040 KB ok, correct split
14 Correct 16 ms 23040 KB ok, correct split
15 Correct 253 ms 47480 KB ok, correct split
16 Correct 204 ms 40572 KB ok, correct split
17 Correct 223 ms 50040 KB ok, correct split
18 Correct 224 ms 46456 KB ok, correct split
19 Correct 267 ms 43128 KB ok, correct split
20 Correct 198 ms 41592 KB ok, correct split
21 Correct 155 ms 40200 KB ok, correct split
22 Correct 155 ms 40184 KB ok, correct split
23 Correct 158 ms 40200 KB ok, correct split
24 Correct 16 ms 23040 KB ok, correct split
25 Correct 205 ms 40552 KB ok, correct split
26 Correct 74 ms 30328 KB ok, correct split
27 Correct 17 ms 23040 KB ok, correct split
28 Correct 213 ms 44280 KB ok, correct split
29 Correct 210 ms 43768 KB ok, correct split
30 Correct 217 ms 44536 KB ok, correct split
31 Correct 225 ms 44920 KB ok, correct split
32 Correct 218 ms 44280 KB ok, correct split
33 Correct 65 ms 29176 KB ok, no valid answer
34 Correct 92 ms 31992 KB ok, no valid answer
35 Correct 188 ms 40196 KB ok, no valid answer
36 Correct 227 ms 40656 KB ok, no valid answer
37 Correct 166 ms 40200 KB ok, no valid answer
38 Correct 16 ms 23040 KB ok, correct split
39 Correct 16 ms 23040 KB ok, no valid answer
40 Correct 16 ms 23040 KB ok, correct split
41 Correct 17 ms 23040 KB ok, correct split
42 Correct 17 ms 23040 KB ok, correct split
43 Correct 16 ms 23040 KB ok, correct split
44 Correct 17 ms 23168 KB ok, correct split
45 Correct 16 ms 23040 KB ok, correct split
46 Correct 20 ms 23552 KB ok, correct split
47 Correct 20 ms 23552 KB ok, correct split
48 Correct 18 ms 23040 KB ok, correct split
49 Correct 20 ms 23544 KB ok, correct split
50 Correct 16 ms 23040 KB ok, correct split
51 Correct 16 ms 23040 KB ok, correct split
52 Correct 17 ms 23040 KB ok, correct split
53 Correct 16 ms 23040 KB ok, correct split
54 Correct 16 ms 23040 KB ok, correct split
55 Correct 16 ms 23040 KB ok, correct split
56 Correct 18 ms 23168 KB ok, correct split
57 Correct 17 ms 23296 KB ok, correct split
58 Correct 20 ms 23552 KB ok, correct split
59 Correct 19 ms 23620 KB ok, correct split
60 Correct 19 ms 23680 KB ok, correct split
61 Correct 19 ms 23552 KB ok, correct split
62 Correct 19 ms 23680 KB ok, correct split
63 Incorrect 20 ms 23552 KB jury found a solution, contestant did not
64 Halted 0 ms 0 KB -