oj.uz

Submission #143704

# Submission time Handle Problem Language Result Execution time Memory
143704 2019-08-14T23:05:13 Z qkxwsm Split the Attractions (IOI19_split) C++14
33 / 100
 118 ms 11856 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
	{
		FOR(i, 0, A) ans[i] = 1;
		FOR(i, A, A + B) ans[i] = 2;
		FOR(i, A + B, A + B + C) ans[i] = 3;
	}
	// cerr << "HUH\n"
	return ans;
}

Subtask #1
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 2684 KB ok, correct split
6 Incorrect 4 ms 2680 KB 3 components are not connected
7 Halted 0 ms 0 KB -

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 9252 KB ok, correct split
5 Correct 74 ms 8312 KB ok, correct split
6 Correct 70 ms 8108 KB ok, correct split
7 Correct 75 ms 8184 KB ok, correct split
8 Correct 118 ms 10492 KB ok, correct split
9 Correct 76 ms 8148 KB ok, correct split
10 Correct 58 ms 8560 KB ok, correct split
11 Correct 61 ms 8592 KB ok, correct split
12 Correct 61 ms 8488 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 93 ms 9080 KB ok, correct split
3 Correct 35 ms 5212 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 109 ms 11028 KB ok, correct split
6 Correct 117 ms 10872 KB ok, correct split
7 Correct 94 ms 10872 KB ok, correct split
8 Correct 99 ms 11856 KB ok, correct split
9 Correct 98 ms 10828 KB ok, correct split
10 Correct 28 ms 4776 KB ok, no valid answer
11 Correct 41 ms 5880 KB ok, no valid answer
12 Correct 71 ms 9204 KB ok, no valid answer
13 Correct 79 ms 9080 KB ok, no valid answer
14 Correct 65 ms 9328 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, no valid answer
3 Correct 4 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB 3 components are not connected
5 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 2684 KB ok, correct split
6 Incorrect 4 ms 2680 KB 3 components are not connected
7 Halted 0 ms 0 KB -