제출 #1290984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290984		gustavo_d	Split the Attractions (IOI19_split)	C++20	29 / 100	72 ms	16204 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

pair<int, int> target[3];
vector<int> adj[MAXN];
vector<int> res;
int subSz[MAXN]; int n;
bool vis[MAXN];

int dfs2(int v, int pai, int get, int c) {
	if (get <= 0) return 0;
	res[v] = c;
	int got = 1;
	vis[v] = true;
	for (int viz : adj[v]) {
		if (vis[viz] or viz == pai) continue;
		got += dfs2(viz, v, get - got, c);
	}
	return got;
}

bool dfs(int v, int pai) {
	// cerr <<  v << endl;
	vis[v] = true;
	subSz[v] = 1;
	for (int viz : adj[v]) {
		if (vis[viz]) continue;
		if (dfs(viz, v)) return true;
		subSz[v] += subSz[viz];
	}

	if (pai == -1) return false;

	if (subSz[v] >= target[0].first and n - subSz[v] >= target[1].first) {
		for (int i=0; i<n; i++) vis[i] = false;
		dfs2(v, pai, target[0].first, target[0].second);
		for (int i=0; i<n; i++) vis[i] = false;
		dfs2(pai, v, target[1].first, target[1].second);
		return true;
	}
	if (n - subSz[v] >= target[0].first and subSz[v] >= target[1].first) {
		for (int i=0; i<n; i++) vis[i] = false;
		dfs2(v, pai, target[1].first, target[1].second);
		for (int i=0; i<n; i++) vis[i] = false;
		dfs2(pai, v, target[0].first, target[0].second);
		return true;
	}

	return false;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;

	for (int i=0; i<n-1; i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	target[0] = make_pair(a, 1);
	target[1] = make_pair(b, 2);
	target[2] = make_pair(c, 3);
	sort(target, target+3);
	
	res = vector<int> (n, -1);

	if (!dfs(0, -1))
		res = vector<int> (n, 0);
	else {
		for (int i=0; i<n; i++) {
			if (res[i] == -1) res[i] = target[2].second;
		}
	}

	return res;
}

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