Submission #826993

#	Time	Username	Problem	Language	Result	Execution time	Memory
826993		vjudge1	Split the Attractions (IOI19_split)	C++17	0 / 100	4 ms	9684 KiB

split

#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

using namespace std;
#define pii pair <int, int>

const int maxn=2e5+10;

int n, m, a, b, c, col[maxn], sz[maxn], ok;
pii dp1[maxn], dp2[maxn];
vector <int> edge[maxn], g[maxn];

void dfs2(int v, int pred, int TT)
{
	if(TT == v) 
	{
		if(a)
		{
			a--;
			col[v] = 1;
		}
	}
	else 
	{
		if(b)
		{
			b--;
			col[v] = 2;
		}
	}
	for(auto to : edge[v])
	{
		if(to == pred) continue;
		if(TT == v)
			dfs2(to, v, to);
		else
			dfs2(to, v, TT);
	}
}

void dfs3(int v, int pred, int TT)
{
	if(TT == v) 
	{
		if(b)
		{
			col[v] = 2;
			b--;
		}
	}
	else 
	{
		if(a)
		{
			a--;
			col[v] = 1;
		}
	}
	for(auto to : edge[v])
	{
		if(to == pred) continue;
		if(TT == v)
			dfs3(to, v, to);
		else
			dfs3(to, v, TT);
	}
}

void dfs(int v, int pred = -1)
{
	sz[v] = 1;
	dp1[v] = {1e9, 1e9};
	dp2[v] = {1e9, 1e9};
	for(auto to : edge[v])
	{
		if(to == pred) continue;
		dfs(to, v);
		if(ok) return;
		sz[v] += sz[to];
		dp1[v] = min(dp1[v], dp1[to]);
		dp2[v] = min(dp2[v], dp2[to]);
	}
	if(sz[v] >= a)
	{
		dp1[v] = min(dp1[v], {sz[v], v});
	}
	if(sz[v] >= b)
	{
		dp2[v] = min(dp2[v], {sz[v], v});
	}
	if(sz[v] - dp1[v].f >= b)
	{
		dfs2(v, pred, dp1[v].s);
		ok = 1;
		return;
	}
	if(sz[v] - dp2[v].f >= a)
	{
		dfs3(v, pred, dp2[v].s);
		ok = 1;
		return;
	}
}

int used[maxn];

void calc(int v)
{
	used[v] = 1;
	for(auto to : g[v])
	{
		if(used[to]) continue;
		g[to].pb(v);
		g[v].pb(to);
		calc(to);
	}
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
	n = N;
	m = q.size();
	forn(1, i, n) edge[i].clear();
	ok =  0;
	FOR(0, i, m)
	{
		q[i]++;
		p[i]++;
		g[q[i]].pb(p[i]);
		g[p[i]].pb(q[i]);
	}
	calc(1);
	vector <pii> sor;
	sor.pb({A, 1});
	sor.pb({B, 2});
	sor.pb({C, 3});
	sort(all(sor));
	a = sor[0].f;
	b = sor[1].f;
	c = sor[2].f;
	dfs(1);
//	cout << a << " " << b << " " << c << endl;
//	forn(1, i, n) cout << col[i] << " ";
//	cout << endl;
	vector <int> res(n, 0);
	if(!ok) return res;
	forn(1, i, n)
	{
		if(col[i] == 0) col[i] = 3;
		res[i-1] = sor[col[i]-1].s;
	}
	return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36