oj.uz

Submission #295475

# Submission time Handle Problem Language Result Execution time Memory
295475 2020-09-09T17:05:30 Z mode149256 Split the Attractions (IOI19_split) C++14
40 / 100
 264 ms 50820 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;

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);
	makeZemyn(x);

	for (auto u : edges[x]) {
		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;
		}
	}

	colored = false;
}

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) {
		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 21 ms 23040 KB ok, correct split
2 Correct 19 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 17 ms 23040 KB ok, correct split
6 Correct 17 ms 23040 KB ok, correct split
7 Correct 250 ms 50452 KB ok, correct split
8 Correct 101 ms 29688 KB ok, correct split
9 Correct 264 ms 46840 KB ok, correct split
10 Correct 95 ms 29688 KB ok, correct split
11 Correct 240 ms 50820 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23060 KB ok, correct split
2 Correct 15 ms 23040 KB ok, correct split
3 Correct 14 ms 23040 KB ok, correct split
4 Correct 111 ms 31480 KB ok, correct split
5 Correct 88 ms 29816 KB ok, correct split
6 Correct 103 ms 29816 KB ok, correct split
7 Correct 93 ms 31992 KB ok, correct split
8 Correct 134 ms 33016 KB ok, correct split
9 Correct 91 ms 29688 KB ok, correct split
10 Correct 83 ms 29680 KB ok, correct split
11 Correct 76 ms 29680 KB ok, correct split
12 Correct 76 ms 30064 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 41336 KB ok, correct split
3 Correct 78 ms 30332 KB ok, correct split
4 Correct 17 ms 23040 KB ok, correct split
5 Correct 221 ms 44852 KB ok, correct split
6 Correct 228 ms 44664 KB ok, correct split
7 Correct 237 ms 45176 KB ok, correct split
8 Correct 250 ms 45688 KB ok, correct split
9 Correct 222 ms 44920 KB ok, correct split
10 Correct 65 ms 29176 KB ok, no valid answer
11 Correct 95 ms 32120 KB ok, no valid answer
12 Correct 184 ms 40960 KB ok, no valid answer
13 Correct 222 ms 41336 KB ok, no valid answer
14 Correct 155 ms 40968 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 17 ms 23040 KB ok, no valid answer
3 Correct 17 ms 23040 KB ok, correct split
4 Correct 16 ms 23040 KB ok, correct split
5 Correct 19 ms 23040 KB ok, correct split
6 Correct 17 ms 23168 KB ok, correct split
7 Correct 16 ms 23040 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 17 ms 23040 KB ok, correct split
12 Correct 20 ms 23552 KB ok, correct split
13 Correct 17 ms 23040 KB ok, correct split
14 Correct 16 ms 23040 KB ok, correct split
15 Runtime error 54 ms 46584 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23040 KB ok, correct split
2 Correct 19 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 17 ms 23040 KB ok, correct split
6 Correct 17 ms 23040 KB ok, correct split
7 Correct 250 ms 50452 KB ok, correct split
8 Correct 101 ms 29688 KB ok, correct split
9 Correct 264 ms 46840 KB ok, correct split
10 Correct 95 ms 29688 KB ok, correct split
11 Correct 240 ms 50820 KB ok, correct split
12 Correct 16 ms 23060 KB ok, correct split
13 Correct 15 ms 23040 KB ok, correct split
14 Correct 14 ms 23040 KB ok, correct split
15 Correct 111 ms 31480 KB ok, correct split
16 Correct 88 ms 29816 KB ok, correct split
17 Correct 103 ms 29816 KB ok, correct split
18 Correct 93 ms 31992 KB ok, correct split
19 Correct 134 ms 33016 KB ok, correct split
20 Correct 91 ms 29688 KB ok, correct split
21 Correct 83 ms 29680 KB ok, correct split
22 Correct 76 ms 29680 KB ok, correct split
23 Correct 76 ms 30064 KB ok, correct split
24 Correct 16 ms 23040 KB ok, correct split
25 Correct 205 ms 41336 KB ok, correct split
26 Correct 78 ms 30332 KB ok, correct split
27 Correct 17 ms 23040 KB ok, correct split
28 Correct 221 ms 44852 KB ok, correct split
29 Correct 228 ms 44664 KB ok, correct split
30 Correct 237 ms 45176 KB ok, correct split
31 Correct 250 ms 45688 KB ok, correct split
32 Correct 222 ms 44920 KB ok, correct split
33 Correct 65 ms 29176 KB ok, no valid answer
34 Correct 95 ms 32120 KB ok, no valid answer
35 Correct 184 ms 40960 KB ok, no valid answer
36 Correct 222 ms 41336 KB ok, no valid answer
37 Correct 155 ms 40968 KB ok, no valid answer
38 Correct 16 ms 23040 KB ok, correct split
39 Correct 17 ms 23040 KB ok, no valid answer
40 Correct 17 ms 23040 KB ok, correct split
41 Correct 16 ms 23040 KB ok, correct split
42 Correct 19 ms 23040 KB ok, correct split
43 Correct 17 ms 23168 KB ok, correct split
44 Correct 16 ms 23040 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 17 ms 23040 KB ok, correct split
49 Correct 20 ms 23552 KB ok, correct split
50 Correct 17 ms 23040 KB ok, correct split
51 Correct 16 ms 23040 KB ok, correct split
52 Runtime error 54 ms 46584 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -