oj.uz

Submission #172081

# Submission time Handle Problem Language Result Execution time Memory
172081 2019-12-31T04:43:21 Z qkxwsm Split the Attractions (IOI19_split) C++14
22 / 100
 279 ms 41760 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, true);
	if (mnmx < X)
	{
		return ans;
	}
	// cerr << "CENTROID " << cent << endl;
	// cerr << "HELLO\n";
	dfs1(cent, N, false);
	// cerr << "CENT " << cent << endl;
	ans[cent] = 2;
	int source = -1;
	// cerr << "segfault\n";
	for (int v : edge1[cent])
	{
		// cerr << "v = " << v << endl;
		if (subtree[v] < X) continue;
		for (int w : edge1[v])
		{
			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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Runtime error 35 ms 29176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Runtime error 34 ms 29308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Correct 222 ms 33144 KB ok, correct split
3 Correct 92 ms 21880 KB ok, correct split
4 Correct 14 ms 14456 KB ok, correct split
5 Correct 223 ms 39412 KB ok, correct split
6 Correct 265 ms 38732 KB ok, correct split
7 Correct 279 ms 38776 KB ok, correct split
8 Correct 276 ms 41760 KB ok, correct split
9 Correct 254 ms 38776 KB ok, correct split
10 Correct 61 ms 20728 KB ok, no valid answer
11 Correct 94 ms 23800 KB ok, no valid answer
12 Correct 167 ms 33780 KB ok, no valid answer
13 Correct 206 ms 33348 KB ok, no valid answer
14 Correct 163 ms 34032 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB ok, correct split
2 Correct 14 ms 14456 KB ok, no valid answer
3 Runtime error 35 ms 29304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 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 Runtime error 35 ms 29176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -