oj.uz

Submission #143702

# Submission time Handle Problem Language Result Execution time Memory
143702 2019-08-14T23:04:41 Z qkxwsm Split the Attractions (IOI19_split) C++14
0 / 100
 90 ms 9336 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;
			}
		}
	}
	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
	}
	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 2808 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
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 90 ms 9336 KB ok, correct split
5 Incorrect 89 ms 9080 KB 2 components are not connected
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB 2 components are not connected
2 Halted 0 ms 0 KB -

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 2808 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 -