Submission #585756

#	Time	Username	Problem	Language	Result	Execution time	Memory
585756		Lucpp	Split the Attractions (IOI19_split)	C++17	100 / 100	118 ms	27152 KiB

split

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

int N, A;

vector<vector<int>> g;
vector<int> num, low;
int dfs_cnt = 0;
bool possible = false;
vector<bool> comp;

void revisit(int u){
	comp[u] = true;
	for(int v : g[u]){
		if(!comp[v] && num[v] > num[u]) revisit(v);
	}
}

int dfs(int u, int par){
	num[u] = low[u] = dfs_cnt++;
	vector<pair<int, int>> must, can;
	int max_subtree = 0;
	for(int v : g[u]){
		if(v == par) continue;
		if(num[v] == -1){
			int size = dfs(v, u);
			max_subtree = max(max_subtree, size);
			if(size == -1) return -1; // answer already found
			low[u] = min(low[u], low[v]);
			if(num[u] <= low[v]) must.emplace_back(size, v);
			else can.emplace_back(size, v);
		}
		else low[u] = min(low[u], num[v]);
	}
	int min_size = 1, max_size = 1;
	for(auto [s, v] : must) min_size += s, max_size += s;
	for(auto [s, v] : can) max_size += s;
	if(min_size <= N-A && max_size >= A && max_subtree < A){
		int size = min_size;
		possible = true;
		comp[u] = true;
		for(auto [s, v] : must) revisit(v);
		for(auto [s, v] : can){
			if(size >= A) break;
			size += s;
			revisit(v);
		}
		return -1;
	}
	return max_size;
}

vector<pair<int, int>> bySize;
vector<int> ans;
vector<bool> vis;
int cnt = 0, cur;
void dfs2(int u){
	vis[u] = true;
	if(cnt < bySize[cur].first){
		cnt++;
		ans[u] = bySize[cur].second;
	}
	else ans[u] = bySize[2].second;
	for(int v : g[u]){
		if(!vis[v] && comp[u] == comp[v]){
			dfs2(v);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	bySize = {{a, 1}, {b, 2}, {c, 3}};
	sort(bySize.begin(), bySize.end());
	g.resize(n);
	for(int i = 0; i < (int)p.size(); i++){
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	N = n;
	A = bySize[0].first;
	num.assign(n, -1);
	low.resize(n);
	comp.resize(n);
	dfs(0, -1);
	if(!possible) return vector<int>(n, 0);
	else{
		ans.resize(n);
		int cn = 0;
		for(int i = 0; i < n; i++) cn += comp[i];
		if(cn < n/2) swap(bySize[0], bySize[1]);
		for(int i = 0; i < 2; i++){
			cur = i; cnt = 0;
			vis.assign(n, false);
			for(int u = 0; u < n; u++){
				if(comp[u] == i){
					dfs2(u);
					break;
				}
			}
		}
		return ans;
	}
}

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