oj.uz

답안 #143699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143699 2019-08-14T23:02:12 Z qkxwsm Split the Attractions (IOI19_split) C++14
33 / 100
 112 ms 12892 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
	}
	// cerr << "HUH\n"
	return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 5 ms 2680 KB ok, correct split
4 Correct 99 ms 9380 KB ok, correct split
5 Correct 90 ms 9052 KB ok, correct split
6 Correct 70 ms 8156 KB ok, correct split
7 Correct 103 ms 12892 KB ok, correct split
8 Correct 112 ms 10552 KB ok, correct split
9 Correct 74 ms 8184 KB ok, correct split
10 Correct 74 ms 9328 KB ok, correct split
11 Correct 71 ms 9328 KB ok, correct split
12 Correct 75 ms 9256 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 88 ms 9080 KB ok, correct split
3 Correct 33 ms 5240 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 95 ms 11128 KB ok, correct split
6 Correct 109 ms 10860 KB ok, correct split
7 Correct 98 ms 10836 KB ok, correct split
8 Correct 109 ms 11720 KB ok, correct split
9 Correct 102 ms 10872 KB ok, correct split
10 Correct 30 ms 4856 KB ok, no valid answer
11 Correct 44 ms 6008 KB ok, no valid answer
12 Correct 75 ms 9204 KB ok, no valid answer
13 Correct 91 ms 9208 KB ok, no valid answer
14 Correct 69 ms 9328 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Incorrect 4 ms 2680 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -