제출 #1103631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103631		_8_8_	Split the Attractions (IOI19_split)	C++17	100 / 100	123 ms	123580 KiB

split

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

using namespace std;
typedef long long ll;

const int N = 1e6 + 12;

vector<int> g[N], gt[N], G[N], res, f[N];
int c[N], s[N];
bool vis[N];
void dfs(int v) {
	s[v] = 1;
	vis[v] = 1;
	for(int to:g[v]) if(!vis[to]) {
		dfs(to);
		gt[v].push_back(to);
		gt[to].push_back(v);
		s[v] += s[to];
	}
}
int n;
int find(int v, int pr = -1) {
	for(int to:gt[v]) {
		if(to != pr && s[to] > n / 2) {
			return find(to, v);
		}
	}
	return v;	
}
vector<pair<int, int>> a;
int bf = 0, t;
void go(int v, int pr) {
	s[t]++;
	c[v] = t;
	f[t].push_back(v);
	for(int to:gt[v]) {
		if(to != pr) {
			go(to, v);
		}
	}
}
vector<int> st;
int sum = 0;
void dfs1(int v) {
	st.push_back(v);
	sum += s[v];
	vis[v] = 1;
	for(int to:G[v]) {
		if(!vis[to]) {
			dfs1(to);
		}
	}
}
bool good[N], used[N];
void col(int v) {
	used[v] = 1;
	if(a[0].first) {
		res[v] = a[0].second;
		--a[0].first;
	}
	for(int to:g[v]) {
		if(good[c[to]] && !used[to]) {
			col(to);
		}
	}
}
void make(int v) {
	vis[v] = 1;
	if(!res[v]) {
		if(a[1].first) {
			a[1].first--;
			res[v] = a[1].second;
		}
	}
	for(int to:g[v]) {
		if(!vis[to] && !res[to]) {
			make(to);
		}
	}
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n;
	res.assign(n, 0);
	for(int i = 0; i < (int)p.size(); i++) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	dfs(0);
	a.push_back({_a, 1});
	a.push_back({_b, 2});
	a.push_back({_c, 3});
	sort(a.begin(), a.end());
	int v = find(0);
	memset(s, 0, sizeof(s));
	for(int to:gt[v]) {
		t++;
		go(to, v);
	}

	for(int i = 0; i < (int)q.size(); i++) {
		int x = c[q[i]], y = c[p[i]];
		if(!x || !y) continue;
		if(x != y) {
			G[x].push_back(y);
			G[y].push_back(x);
		}
	}
	memset(vis, 0, sizeof(vis));
	bool fnd = 0;
	for(int i = 1; i <= t; i++) {
		if(!vis[i]) {
			dfs1(i);
			if(sum < a[0].first) {
				sum = 0;
				st.clear();
				continue;
			}
			sort(st.begin(), st.end(), [&](int x, int y){
				return s[x] > s[y];
			});
			fnd = 1;
			sum = 0;
			for(int j = 0; j < (int)st.size() && sum < a[0].first; j++) {
				sum += s[st[j]];
				good[st[j]] = 1;
			}
			assert(sum <= (n + 1) / 2);
			col(f[st[0]][0]);
			break;
		}
	}
	if(!fnd) {
		return res;
	}
	memset(vis, 0, sizeof(vis));
	make(v);
	for(int i = 0; i < n; i++) {
		if(!res[i]) {
			res[i] = a[2].second;
		}
	}
	return res;
}

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