제출 #1290705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290705		julia_08	Split the Attractions (IOI19_split)	C++20	0 / 100	71 ms	127172 KiB

split

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

using namespace std;

const int MAXN = 1e5 + 10;

vector<int> split, ord;

set<int> marc[MAXN];

int pre[MAXN], pos[MAXN], id[MAXN], sub[MAXN];

vector<int> adj[MAXN];

vector<int> ans;

pair<int, int> first_split, second_split;

int n, t = 0;

void dfs_1(int v, int p){

	sub[v] = 1;

	pre[v] = ++t;
	id[pre[v]] = v;

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

	for(auto u : adj[v]){
		if(u != p){
			if(n - sub[v] == split[0] && sub[u] == split[1]) first_split = {v, u};
		}
	}

	pos[v] = t;

}

void dfs_2(int v, int p){

	marc[sub[v]].erase(pre[v]);

	if(sub[v] == split[0] && !marc[split[1]].empty()){

		int cand_l = *marc[split[1]].begin(), cand_r = *marc[split[1]].rbegin();

		if(cand_l < pre[v]){
			second_split = {v, id[cand_l]};
		} else if(cand_r > pre[v]) second_split = {v, id[cand_r]};

	}

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

	marc[sub[v]].insert(pre[v]);

}

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

bool check(){

	dfs_1(0, 0);

	if(first_split.first != -1){

		auto [v, u] = first_split;

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

		return true;

	}

	for(int i=0; i<n; i++) marc[sub[i]].insert(pre[i]);

	dfs_2(0, 0);

	if(second_split.first != -1){

		auto [v, u] = second_split;

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

		return true;

	}

	return false;

}

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

	n = n_;
	ans.resize(n);

	first_split = second_split = {-1, -1};

	split = {a, b, c};
	ord = {1, 2, 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;

	do{

		ok |= check();

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

	return ans;

}

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