oj.uz

Submission #172083

# Submission time Handle Problem Language Result Execution time Memory
172083 2019-12-31T04:49:27 Z qkxwsm Split the Attractions (IOI19_split) C++14
40 / 100
 339 ms 51412 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 200013

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, X, Y, T, C;
int siz[3];
pii inds;
vi edge[MAXN], edge1[MAXN];
vi ans;
int st[MAXN], ft[MAXN];
bitset<MAXN> seen;
vi bcc[MAXN];
int parent[MAXN], subtree[MAXN];
vpi edges;
int mnmx, cent;

void dfs(int u, int p)
{
	st[u] = T;
	ft[u] = T;
	T++;
	seen[u] = true;
	for (int v : edge[u])
	{
		if (v == p) continue;
		if (seen[v])
		{
			if (st[v] > st[u]) continue;
			edges.PB({u, v});
			ckmin(ft[u], st[v]);
			continue;
		}
		edges.PB({u, v});
		dfs(v, u);
		ckmin(ft[u], ft[v]);
		if (ft[v] >= st[u])
		{
			while(!edges.empty())
			{
				pii p = edges.back();
				edges.pop_back();
				bcc[p.fi].PB(C);
				bcc[p.se].PB(C);
				if (p == MP(u, v)) break;
			}
			C++;
		}
	}
}
void dfs1(int u, int p, bool flag)
{
	subtree[u] = (u < N);
	for (int v : edge1[u])
	{
		if (v == p) continue;
		parent[v] = u;
		dfs1(v, u, flag);
		subtree[u] += subtree[v];
	}
	if (u < N && flag)
	{
		int sz = N - 1, mx = 0;
		vi szs;
		for (int v : edge1[u])
		{
			ckmax(mx, subtree[v]);
			sz -= subtree[v];
		}
		ckmax(mx, sz);
		if (mx < mnmx)
		{
			mnmx = mx;
			cent = u;
		}
	}
	return;
}

vi find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	N = n;
	ans.resize(N);
	siz[0] = a; siz[1] = b; siz[2] = c;
	if (c >= a && c >= b) inds = {0, 1};
	if (b >= a && b >= c) inds = {0, 2};
	if (a >= b && a >= c) inds = {1, 2};
	X = siz[inds.fi]; Y = siz[inds.se];
	if (X > Y)
	{
		swap(inds.fi, inds.se);
		swap(X, Y);
	}
	FOR(i, 0, SZ(p))
	{
		int u = p[i], v = q[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	dfs(0, N);
	FOR(i, 0, N)
	{
		sort(ALL(bcc[i]));
		bcc[i].erase(unique(ALL(bcc[i])), bcc[i].end());
		for (int x : bcc[i])
		{
			// cerr << "EDGE " << i << " -> " << x + N << endl;
			edge1[i].PB(x + N);
			edge1[x + N].PB(i);
		}
	}
	mnmx = N;
	dfs1(0, N + C, true);
	if (mnmx < X)
	{
		return ans;
	}
	// cerr << "CENTROID " << cent << endl;
	// cerr << "HELLO\n";
	dfs1(cent, N + C, false);
	// cerr << "CENT " << cent << endl;
	ans[cent] = 2;
	int source = -1;
	// cerr << "segfault\n";
	for (int v : edge1[cent])
	{
		// cerr << "v = " << v << "subtree = " << subtree[v] << endl;
		if (subtree[v] < X) continue;
		for (int w : edge1[v])
		{
			// cerr << "w = " << w << endl;
			if (w != cent) source = w;
		}
	}
	// cerr << "SOURCE " << source << endl;
	q.clear();
	ans[source] = 1;
	q.PB(source);
	X--;
	while(X > 0)
	{
		int u = q.back(); q.pop_back();
		for (int v : edge[u])
		{
			if (ans[v]) continue;
			ans[v] = 1;
			q.PB(v);
			X--;
			if (X == 0) break;
		}
	}
	q.clear();
	ans[cent] = 2;
	q.PB(cent);
	Y--;
	while(Y > 0)
	{
		int u = q.back(); q.pop_back();
		for (int v : edge[u])
		{
			if (ans[v]) continue;
			ans[v] = 2;
			q.PB(v);
			Y--;
			if (Y == 0) break;
		}
	}
	//1 -> inds.fi
	//2 -> inds.se
	//0 -> 3 - inds.fi - inds.se
	FOR(i, 0, N)
	{
		if (ans[i] == 0)
		{
			ans[i] = 4 - inds.fi - inds.se;
		}
		else if (ans[i] == 1)
		{
			ans[i] = inds.fi + 1;
		}
		else if (ans[i] == 2)
		{
			ans[i] = inds.se + 1;
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Correct 14 ms 14460 KB ok, correct split
3 Correct 15 ms 14456 KB ok, correct split
4 Correct 14 ms 14460 KB ok, correct split
5 Correct 14 ms 14456 KB ok, correct split
6 Correct 14 ms 14456 KB ok, correct split
7 Correct 280 ms 51412 KB ok, correct split
8 Correct 273 ms 45908 KB ok, correct split
9 Correct 291 ms 44148 KB ok, correct split
10 Correct 146 ms 39500 KB ok, correct split
11 Correct 152 ms 39532 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB ok, correct split
2 Correct 14 ms 14460 KB ok, correct split
3 Correct 18 ms 14456 KB ok, correct split
4 Correct 249 ms 37512 KB ok, correct split
5 Correct 240 ms 33144 KB ok, correct split
6 Correct 142 ms 39408 KB ok, correct split
7 Correct 252 ms 45292 KB ok, correct split
8 Correct 207 ms 33400 KB ok, correct split
9 Correct 150 ms 29432 KB ok, correct split
10 Correct 167 ms 33612 KB ok, correct split
11 Correct 180 ms 33648 KB ok, correct split
12 Correct 174 ms 34160 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB ok, correct split
2 Correct 235 ms 32004 KB ok, correct split
3 Correct 76 ms 21496 KB ok, correct split
4 Correct 15 ms 14456 KB ok, correct split
5 Correct 267 ms 38260 KB ok, correct split
6 Correct 339 ms 37536 KB ok, correct split
7 Correct 246 ms 37496 KB ok, correct split
8 Correct 254 ms 40500 KB ok, correct split
9 Correct 266 ms 37548 KB ok, correct split
10 Correct 61 ms 20344 KB ok, no valid answer
11 Correct 100 ms 23288 KB ok, no valid answer
12 Correct 175 ms 32500 KB ok, no valid answer
13 Correct 227 ms 32120 KB ok, no valid answer
14 Correct 230 ms 32888 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14456 KB ok, correct split
2 Correct 14 ms 14456 KB ok, no valid answer
3 Correct 14 ms 14456 KB ok, correct split
4 Correct 15 ms 14456 KB ok, correct split
5 Correct 18 ms 14456 KB ok, correct split
6 Correct 15 ms 14456 KB ok, correct split
7 Correct 18 ms 14456 KB ok, correct split
8 Correct 14 ms 14456 KB ok, correct split
9 Correct 18 ms 15096 KB ok, correct split
10 Correct 18 ms 14840 KB ok, correct split
11 Correct 15 ms 14460 KB ok, correct split
12 Correct 18 ms 14968 KB ok, correct split
13 Correct 15 ms 14456 KB ok, correct split
14 Correct 15 ms 14456 KB ok, correct split
15 Correct 15 ms 14456 KB ok, correct split
16 Correct 15 ms 14456 KB ok, correct split
17 Correct 15 ms 14456 KB ok, correct split
18 Runtime error 35 ms 29176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Correct 14 ms 14460 KB ok, correct split
3 Correct 15 ms 14456 KB ok, correct split
4 Correct 14 ms 14460 KB ok, correct split
5 Correct 14 ms 14456 KB ok, correct split
6 Correct 14 ms 14456 KB ok, correct split
7 Correct 280 ms 51412 KB ok, correct split
8 Correct 273 ms 45908 KB ok, correct split
9 Correct 291 ms 44148 KB ok, correct split
10 Correct 146 ms 39500 KB ok, correct split
11 Correct 152 ms 39532 KB ok, correct split
12 Correct 15 ms 14456 KB ok, correct split
13 Correct 14 ms 14460 KB ok, correct split
14 Correct 18 ms 14456 KB ok, correct split
15 Correct 249 ms 37512 KB ok, correct split
16 Correct 240 ms 33144 KB ok, correct split
17 Correct 142 ms 39408 KB ok, correct split
18 Correct 252 ms 45292 KB ok, correct split
19 Correct 207 ms 33400 KB ok, correct split
20 Correct 150 ms 29432 KB ok, correct split
21 Correct 167 ms 33612 KB ok, correct split
22 Correct 180 ms 33648 KB ok, correct split
23 Correct 174 ms 34160 KB ok, correct split
24 Correct 15 ms 14456 KB ok, correct split
25 Correct 235 ms 32004 KB ok, correct split
26 Correct 76 ms 21496 KB ok, correct split
27 Correct 15 ms 14456 KB ok, correct split
28 Correct 267 ms 38260 KB ok, correct split
29 Correct 339 ms 37536 KB ok, correct split
30 Correct 246 ms 37496 KB ok, correct split
31 Correct 254 ms 40500 KB ok, correct split
32 Correct 266 ms 37548 KB ok, correct split
33 Correct 61 ms 20344 KB ok, no valid answer
34 Correct 100 ms 23288 KB ok, no valid answer
35 Correct 175 ms 32500 KB ok, no valid answer
36 Correct 227 ms 32120 KB ok, no valid answer
37 Correct 230 ms 32888 KB ok, no valid answer
38 Correct 17 ms 14456 KB ok, correct split
39 Correct 14 ms 14456 KB ok, no valid answer
40 Correct 14 ms 14456 KB ok, correct split
41 Correct 15 ms 14456 KB ok, correct split
42 Correct 18 ms 14456 KB ok, correct split
43 Correct 15 ms 14456 KB ok, correct split
44 Correct 18 ms 14456 KB ok, correct split
45 Correct 14 ms 14456 KB ok, correct split
46 Correct 18 ms 15096 KB ok, correct split
47 Correct 18 ms 14840 KB ok, correct split
48 Correct 15 ms 14460 KB ok, correct split
49 Correct 18 ms 14968 KB ok, correct split
50 Correct 15 ms 14456 KB ok, correct split
51 Correct 15 ms 14456 KB ok, correct split
52 Correct 15 ms 14456 KB ok, correct split
53 Correct 15 ms 14456 KB ok, correct split
54 Correct 15 ms 14456 KB ok, correct split
55 Runtime error 35 ms 29176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Halted 0 ms 0 KB -