Submission #585714

#	Time	Username	Problem	Language	Result	Execution time	Memory
585714		Lucpp	Split the Attractions (IOI19_split)	C++17	0 / 100	59 ms	11392 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(num[v] > num[u]) revisit(v);
	}
}

int dfs(int u, int par){
	num[u] = low[u] = dfs_cnt++;
	vector<pair<int, int>> must, can;
	for(int v : g[u]){
		if(v == par) continue;
		if(num[v] == -1){
			int size = dfs(v, u);
			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){
		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<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<pair<int, int>> 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{
		vector<int> ans(n);
		int cnt = 0;
		for(int i = 0; i < n; i++) cnt += comp[i];
		if(cnt > n/2) swap(bySize[0], bySize[1]);
		int cnt1 = 0, cnt2 = 0;
		for(int i = 0; i < n; i++){
			if(comp[i]){
				if(cnt1 < bySize[0].first){
					cnt1++;
					ans[i] = bySize[0].second;
				}
				else ans[i] = bySize[2].second;
			}
			else{
				if(cnt2 < bySize[1].first){
					cnt2++;
					ans[i] = bySize[1].second;
				}
				else ans[i] = bySize[2].second;
			}
		}
		return ans;
	}
}

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