oj.uz

Submission #294807

# Submission time Handle Problem Language Result Execution time Memory
294807 2020-09-09T09:43:48 Z mode149256 Split the Attractions (IOI19_split) C++14
29 / 100
 143 ms 16124 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;
vii edges(MX);
vi col(3);
vi kiek(3);
vi sz(MX, 0);
vi res;
vb been(MX, false);

bool colored = false;

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

	for (auto u : edges[x]) {
		if (been[u]) continue;
		makeSz(u);
		sz[x] += sz[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)
			color(u, x, c);
}

void dfs(int x, int p) {
	// rooted at x
	for (auto u : edges[x]) {
		if (sz[u] >= kiek[0] and N - sz[u] >= kiek[1]) {
			colored = true;
			color(u, x, 0);
			color(x, u, 1);
			return;
		} else if (sz[u] >= kiek[1] and N - sz[u] >= kiek[0]) {
			colored = true;
			color(u, x, 1);
			color(x, u, 0);
			return;
		}
	}

	for (auto u : edges[x]) {
		if (u == p) 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 < M; ++i)
	{
		edges[p[i]].emplace_back(q[i]);
		edges[q[i]].emplace_back(p[i]);
	}

	sortabc();

	if (kiek[0] == 1) {
		color(0, -1, 1);
		for (int i = 0; i < N; ++i)
		{
			if (!res[i]) {
				res[i] = col[0];
				break;
			}
		}
		for (int i = 0; i < N; ++i)
		{
			if (!res[i])
				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 4 ms 6016 KB ok, correct split
2 Correct 4 ms 5888 KB ok, correct split
3 Correct 4 ms 5888 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 4 ms 5888 KB ok, correct split
6 Correct 4 ms 5888 KB ok, correct split
7 Correct 111 ms 15736 KB ok, correct split
8 Correct 75 ms 11256 KB ok, correct split
9 Correct 101 ms 13944 KB ok, correct split
10 Correct 80 ms 11256 KB ok, correct split
11 Correct 115 ms 16124 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB ok, correct split
2 Correct 4 ms 5888 KB ok, correct split
3 Correct 4 ms 5888 KB ok, correct split
4 Correct 102 ms 12408 KB ok, correct split
5 Correct 79 ms 11388 KB ok, correct split
6 Correct 81 ms 11272 KB ok, correct split
7 Correct 87 ms 13688 KB ok, correct split
8 Incorrect 141 ms 15096 KB invalid split: #1=1, #2=23, #3=99976
9 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB ok, correct split
2 Correct 100 ms 11384 KB ok, correct split
3 Correct 36 ms 8056 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 105 ms 12920 KB ok, correct split
6 Correct 138 ms 12664 KB ok, correct split
7 Correct 116 ms 13560 KB ok, correct split
8 Correct 119 ms 13944 KB ok, correct split
9 Correct 143 ms 13304 KB ok, correct split
10 Correct 27 ms 7680 KB ok, no valid answer
11 Correct 44 ms 8568 KB ok, no valid answer
12 Correct 77 ms 11636 KB ok, no valid answer
13 Correct 93 ms 11384 KB ok, no valid answer
14 Correct 67 ms 11664 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB ok, correct split
2 Correct 4 ms 5888 KB ok, no valid answer
3 Correct 4 ms 5888 KB ok, correct split
4 Incorrect 4 ms 5888 KB invalid split: #1=5, #2=2, #3=4
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6016 KB ok, correct split
2 Correct 4 ms 5888 KB ok, correct split
3 Correct 4 ms 5888 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 4 ms 5888 KB ok, correct split
6 Correct 4 ms 5888 KB ok, correct split
7 Correct 111 ms 15736 KB ok, correct split
8 Correct 75 ms 11256 KB ok, correct split
9 Correct 101 ms 13944 KB ok, correct split
10 Correct 80 ms 11256 KB ok, correct split
11 Correct 115 ms 16124 KB ok, correct split
12 Correct 4 ms 5888 KB ok, correct split
13 Correct 4 ms 5888 KB ok, correct split
14 Correct 4 ms 5888 KB ok, correct split
15 Correct 102 ms 12408 KB ok, correct split
16 Correct 79 ms 11388 KB ok, correct split
17 Correct 81 ms 11272 KB ok, correct split
18 Correct 87 ms 13688 KB ok, correct split
19 Incorrect 141 ms 15096 KB invalid split: #1=1, #2=23, #3=99976
20 Halted 0 ms 0 KB -