제출 #1005768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005768		12345678	Split the Attractions (IOI19_split)	C++17	0 / 100	587 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int N, sz[nx], f, cnt;
vector<int> d[nx], t, res;

void dfs2(int u, int p, int x)
{
	res[u]=x;
	cnt--;
	for (auto v:d[u]) if (v!=p&&cnt>0) dfs2(v, u, x);
}
void dfs(int u, int p)
{
	sz[u]=1;
	for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
	if (p!=u&&!f&&min(sz[u], N-sz[u])>=t[0]&&max(sz[u], N-sz[u])>=t[1]) 
	{
		int a=sz[u], b=N-sz[u];
		f=1;
		if (a<=b)
		{
			cnt=t[0];
			dfs2(u, p, 1);
			cnt=t[1];
			dfs2(p, u, 2);
		}
		else
		{
			cnt=t[0];
			dfs2(p, u, 1);
			cnt=t[1];
			dfs2(u, p, 2);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n;
	res.resize(n);
	for (int i=0; i<n; i++) res[i]=3;
	t.push_back(a), t.push_back(b), t.push_back(c);
	sort(t.begin(), t.end());
	for (int i=0; i<n-1; i++) d[p[i]].push_back(q[i]), d[q[i]].push_back(p[i]);
	dfs(0, 0);
	if (!f) for (int i=0; i<n; i++) res[i]=0;
	return res;
}

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