Submission #1197733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197733		tkm_algorithms	Split the Attractions (IOI19_split)	C++20	0 / 100	2095 ms	4928 KiB

split

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "split.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const char nl = '\n';

int tutu;
const int N = 2e5+10;
vector<int> g[N];
vector<pair<int, int>> arr;
int tin[N], tout[N];
int ss[N], cut[N];
int vis[N];

void dfs(int a, int p) {
	tin[a] = tout[a] = tutu++;
	ss[a] = 1;
	//vis[a] = 1;
	for (auto i: g[a]) {
		if (i == p)continue;
		if (!tin[i]) {
			dfs(i, a);
			ss[a] += ss[i];
			tout[a] = min(tout[a], tout[i]);
			continue;
		}
		tout[a] = min(tout[a], tin[i]);
	}
}

int centroid(int u, int p) {
	for (auto i: g[u])if (ss[i] >= arr[0].first)return centroid(i, u);
	return u;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	tutu = 1; int m = sz(p);
	for (int i = 0; i < m; ++i) {
		g[q[i]].push_back(p[i]);
		g[p[i]].push_back(q[i]);
	}
	arr.push_back({a, 1});
	arr.push_back({b, 2});
	arr.push_back({c, 3});
	sort(all(arr));
	vector<int> ans(n, arr[2].second);
	function<void(int)> color_1 = [&](int u)
    {
        if (arr[1].first)ans[u] = arr[1].second, --arr[1].first;
        vis[u] = 1;
        for (auto i: g[u])color_1(i);
    };
    function<void(int)> color_0 = [&](int u)
    {
        if (arr[0].first)ans[u] = arr[0].second, --arr[0].first;
        vis[u] = 1;
        for (auto i: g[u])if (!vis[i])color_0(i);
    };
    dfs(0, 0);
	int fnd = centroid(0, 0);
	//cout << fnd << nl;
	for (auto i: g[fnd]) {
		if (ss[i] >= arr[0].first)continue; // parent
		if (tout[i] < tin[fnd]) { // back edge
			if (ss[fnd]-ss[i] >= arr[0].first)ss[fnd] -= ss[i], cut[i] = 1;
		}
	}
	if(n - ss[fnd] >= arr[1].first) swap(arr[0], arr[1]);
    if(n - ss[fnd] >= arr[0].first) {
		--arr[1].first;
		vis[fnd] = 1;
		ans[fnd] = arr[1].second;
		for (auto i: g[fnd])if (!cut[i])color_1(i);
		for (int i = 0; i < n; ++i) {
			if (!vis[i]) {
				color_0(i);
				break;
			}
		}
	} else return vector<int>(n, 0);
	return ans;
}

//void solve() {
	//int n, m; cin >> n >> m;
	//int a, b, c;
	//cin >> a >> b >> c;
	//vector<int> u(m), v(m);
	//for (int i = 0; i < m; ++i)cin >> u[i] >> v[i];
	//vector<int> ans = find_split(n, a, b, c, u, v);
	//for (auto i: ans)cout << i << " ";
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //int t = 1;
    //for (int _ = 0; _ < t; ++_) {
        //solve();
    //}
    //return 0;
//}

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