oj.uz

Submission #143708

# Submission time Handle Problem Language Result Execution time Memory
143708 2019-08-14T23:08:40 Z qkxwsm Split the Attractions (IOI19_split) C++14
40 / 100
 113 ms 14940 KB 
#include "split.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 100013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, A, B, C, M, R;
int Z[3];
vi edge[MAXN];
vi ans;
int subtree[MAXN], parent[MAXN];
array<int, 3> ord;

void dfs(int u, int p)
{
	subtree[u] = 1;
	for (int v : edge[u])
	{
		if (v == p) continue;
		parent[v] = u; dfs(v, u);
		subtree[u] += subtree[v];
	}
}

vi find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	N = n; A = a; B = b; C = c; ans.resize(N); M = SZ(p); Z[0] = A; Z[1] = B; Z[2] = C;
	if (A <= B && B <= C) ord = {1, 2, 3};
	if (A <= C && C <= B) ord = {1, 3, 2};
	if (B <= A && A <= C) ord = {2, 1, 3};
	if (B <= C && C <= A) ord = {2, 3, 1};
	if (C <= B && B <= A) ord = {3, 1, 2};
	if (C <= A && A <= B) ord = {3, 2, 1};
	FOR(i, 0, SZ(p))
	{
		int u = p[i], v = q[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	FOR(i, 0, N) ans[i] = 0;
	if (a == 1)
	{
		q.clear(); q.PB(0); b = 0;
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = 2; b++;
			// cerr << "MARK " << u << endl;
			if (b == B) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					// cerr << u << " -> " << v << endl;
					ans[v] = -2;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] != 2) ans[i] = 3;
		}
		FOR(i, 0, N)
		{
			if (ans[i] == 3)
			{
				ans[i] = 1;
				break;
			}
		}
	}
	else if (M == N - 1)
	{
		parent[0] = N;
		dfs(0, N);
		R = -1;
		FOR(i, 0, N)
		{
			int sum = N - 1, mx = 0;
			for (int v : edge[i])
			{
				if (v == parent[i]) continue;
				sum -= subtree[v];
				ckmax(mx, subtree[v]);
			}
			ckmax(mx, sum);
			if (mx <= N / 2) R = i;
		}
		parent[R] = N;
		dfs(R, N);
		//there has to be a connected block that doesn't contain the centroid.
		int mx = 0, ch = -1;
		for (int v : edge[R])
		{
			if (subtree[v] > mx)
			{
				mx = subtree[v];
				ch = v;
			}
		}
		int sz = Z[ord[0] - 1];
		if (mx < sz) return ans;
		//generate any set lol
		ans[R] = -1;
		q.clear(); q.PB(ch);
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = -2; sz--; if (sz == 0) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ans[v] = -1;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] == -2) ans[i] = ord[0];
			else ans[i] = 0;
		}
		q.clear(); q.PB(R);
		sz = Z[ord[1] - 1];
		while(!q.empty())
		{
			int u = q.back(); q.pop_back();
			ans[u] = -2; sz--; if (sz == 0) break;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ans[v] = -1;
					q.PB(v);
				}
			}
		}
		FOR(i, 0, N)
		{
			if (ans[i] == -2) ans[i] = ord[1];
		}
		FOR(i, 0, N)
		{
			if (ans[i] != ord[0] && ans[i] != ord[1]) ans[i] = ord[2];
		}
		//do the exact smae thing except for ord1
	}
	else
	{
		vi ord; ord.PB(0);
		FOR(i, 0, N)
		{
			int u = ord.back(); ans[u] = -1;
			for (int v : edge[u])
			{
				if (ans[v] == 0)
				{
					ord.PB(v);
					break;
				}
			}
		}
		FOR(i, 0, A) ans[ord[i]] = 1;
		FOR(i, A, A + B) ans[ord[i]] = 2;
		FOR(i, A + B, A + B + C) ans[ord[i]] = 3;
	}
	// cerr << "HUH\n"
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 107 ms 14940 KB ok, correct split
8 Correct 75 ms 8184 KB ok, correct split
9 Correct 102 ms 12552 KB ok, correct split
10 Correct 67 ms 8184 KB ok, correct split
11 Correct 77 ms 8440 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 93 ms 9264 KB ok, correct split
5 Correct 70 ms 8340 KB ok, correct split
6 Correct 67 ms 8184 KB ok, correct split
7 Correct 89 ms 8148 KB ok, correct split
8 Correct 113 ms 10520 KB ok, correct split
9 Correct 70 ms 8184 KB ok, correct split
10 Correct 59 ms 8560 KB ok, correct split
11 Correct 59 ms 8580 KB ok, correct split
12 Correct 62 ms 8560 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 85 ms 9080 KB ok, correct split
3 Correct 34 ms 5496 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 95 ms 10972 KB ok, correct split
6 Correct 105 ms 10872 KB ok, correct split
7 Correct 98 ms 10872 KB ok, correct split
8 Correct 97 ms 11896 KB ok, correct split
9 Correct 91 ms 10872 KB ok, correct split
10 Correct 27 ms 4856 KB ok, no valid answer
11 Correct 38 ms 5884 KB ok, no valid answer
12 Correct 70 ms 9204 KB ok, no valid answer
13 Correct 79 ms 9052 KB ok, no valid answer
14 Correct 67 ms 9328 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB answer contains both zero and positive values
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 107 ms 14940 KB ok, correct split
8 Correct 75 ms 8184 KB ok, correct split
9 Correct 102 ms 12552 KB ok, correct split
10 Correct 67 ms 8184 KB ok, correct split
11 Correct 77 ms 8440 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 93 ms 9264 KB ok, correct split
16 Correct 70 ms 8340 KB ok, correct split
17 Correct 67 ms 8184 KB ok, correct split
18 Correct 89 ms 8148 KB ok, correct split
19 Correct 113 ms 10520 KB ok, correct split
20 Correct 70 ms 8184 KB ok, correct split
21 Correct 59 ms 8560 KB ok, correct split
22 Correct 59 ms 8580 KB ok, correct split
23 Correct 62 ms 8560 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Correct 85 ms 9080 KB ok, correct split
26 Correct 34 ms 5496 KB ok, correct split
27 Correct 4 ms 2680 KB ok, correct split
28 Correct 95 ms 10972 KB ok, correct split
29 Correct 105 ms 10872 KB ok, correct split
30 Correct 98 ms 10872 KB ok, correct split
31 Correct 97 ms 11896 KB ok, correct split
32 Correct 91 ms 10872 KB ok, correct split
33 Correct 27 ms 4856 KB ok, no valid answer
34 Correct 38 ms 5884 KB ok, no valid answer
35 Correct 70 ms 9204 KB ok, no valid answer
36 Correct 79 ms 9052 KB ok, no valid answer
37 Correct 67 ms 9328 KB ok, no valid answer
38 Incorrect 4 ms 2680 KB answer contains both zero and positive values
39 Halted 0 ms 0 KB -