Submission #1290725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290725		julia_08	Split the Attractions (IOI19_split)	C++20	0 / 100	584 ms	1114112 KiB

split

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

using namespace std;

const int MAXN = 2e5 + 10;

vector<pair<int, int>> split;

int pre[MAXN], pos[MAXN];

int sub[MAXN], pai[MAXN];

vector<int> adj[MAXN];

vector<int> ans;

int n, t = 0;

void dfs_1(int v, int p){

	sub[v] = 1;

	for(auto u : adj[v]){
		if(u != p){

			pai[u] = v;
			dfs_1(u, v);
			sub[v] += sub[u];

		}
	}

}

void dfs_2(int v, int p){

	pre[v] = ++t;

	for(auto u : adj[v]){
		if(u != p){
			dfs_2(u, v);
		}
	}

	pos[v] = t;

}

bool is_sub(int a, int b){
	return pre[b] <= pre[a] && pos[a] <= pos[b];
}

bool check(){

	int root = -1, v = -1, u = -1;

	for(int i=0; i<n; i++){

		int cur_v = -1, cur_u = -1;

		for(auto j : adj[i]){

			if(j != pai[i]){

				if(cur_v == -1 && sub[j] == split[0].first){
					cur_v = j;
				} else if(cur_u == -1 && sub[j] == split[1].first) cur_u = j;

			} else{

				if(cur_v == -1 && n - sub[i] == split[0].first){
					cur_v = j;
				} else if(cur_u == -1 && n - sub[i] == split[1].first) cur_u = j;

			}

		}

		if(cur_v != -1 && cur_u != -1){
			v = cur_v; u = cur_u;
			root = i;
			break;
		}

	}

	if(root == -1) return false;

	t = 0;

	dfs_2(root, root);

	for(int i=0; i<n; i++){
		if(is_sub(i, v)){
			ans[i] = split[0].second;
		} else if(is_sub(i, u)){
			ans[i] = split[1].second;
		} else ans[i] = split[2].second;
	}

	return true;

}

vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q){

	n = n_;
	ans.resize(n);

	for(int i=0; i<n; i++) ans[i] = 0;

	split = {{a, 1}, {b, 2}, {c, 3}};

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

	sort(split.begin(), split.end());

	bool ok = false;

	dfs_1(0, 0);

	do{

		ok |= check();

	} while(!ok && next_permutation(split.begin(), split.end()));

	return ans;

}

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