oj.uz

Submission #294822

# Submission time Handle Problem Language Result Execution time Memory
294822 2020-09-09T09:48:23 Z mode149256 Split the Attractions (IOI19_split) C++14
29 / 100
 137 ms 16012 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);
		assert(kiek[1] == 0);
		for (int i = 0; i < N; ++i)
		{
			if (!res[i]) {
				if (kiek[0]) {
					assert(kiek[0] == 1);
					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 5 ms 5888 KB ok, correct split
2 Correct 4 ms 5888 KB ok, correct split
3 Correct 5 ms 5888 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 5 ms 5888 KB ok, correct split
6 Correct 5 ms 5864 KB ok, correct split
7 Correct 137 ms 15736 KB ok, correct split
8 Correct 83 ms 11256 KB ok, correct split
9 Correct 111 ms 13976 KB ok, correct split
10 Correct 78 ms 11256 KB ok, correct split
11 Correct 120 ms 16012 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5888 KB ok, correct split
2 Correct 5 ms 5888 KB ok, correct split
3 Correct 5 ms 5888 KB ok, correct split
4 Correct 104 ms 12408 KB ok, correct split
5 Correct 74 ms 11384 KB ok, correct split
6 Correct 81 ms 11256 KB ok, correct split
7 Correct 86 ms 13688 KB ok, correct split
8 Incorrect 125 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 107 ms 11384 KB ok, correct split
3 Correct 30 ms 8064 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 116 ms 12920 KB ok, correct split
6 Correct 107 ms 12668 KB ok, correct split
7 Correct 107 ms 13560 KB ok, correct split
8 Correct 121 ms 13888 KB ok, correct split
9 Correct 124 ms 13316 KB ok, correct split
10 Correct 27 ms 7672 KB ok, no valid answer
11 Correct 50 ms 8568 KB ok, no valid answer
12 Correct 81 ms 11636 KB ok, no valid answer
13 Correct 99 ms 11504 KB ok, no valid answer
14 Correct 70 ms 11632 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 5 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 5 ms 5888 KB ok, correct split
2 Correct 4 ms 5888 KB ok, correct split
3 Correct 5 ms 5888 KB ok, correct split
4 Correct 4 ms 5888 KB ok, correct split
5 Correct 5 ms 5888 KB ok, correct split
6 Correct 5 ms 5864 KB ok, correct split
7 Correct 137 ms 15736 KB ok, correct split
8 Correct 83 ms 11256 KB ok, correct split
9 Correct 111 ms 13976 KB ok, correct split
10 Correct 78 ms 11256 KB ok, correct split
11 Correct 120 ms 16012 KB ok, correct split
12 Correct 5 ms 5888 KB ok, correct split
13 Correct 5 ms 5888 KB ok, correct split
14 Correct 5 ms 5888 KB ok, correct split
15 Correct 104 ms 12408 KB ok, correct split
16 Correct 74 ms 11384 KB ok, correct split
17 Correct 81 ms 11256 KB ok, correct split
18 Correct 86 ms 13688 KB ok, correct split
19 Incorrect 125 ms 15096 KB invalid split: #1=1, #2=23, #3=99976
20 Halted 0 ms 0 KB -