Submission #292175

#	Time	Username	Problem	Language	Result	Execution time	Memory
292175		PeppaPig	Split the Attractions (IOI19_split)	C++14	33 / 100	175 ms	19064 KiB

split

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

using namespace std;

const int N = 1e5 + 5;

struct UnionFind {
	int par[N], sz[N];

	void init() {
		iota(par, par + N, 0);
		fill_n(sz, N, 1);
	}

	int find(int x) { return par[x] = x == par[x] ? x : find(par[x]); }

	void unite(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		par[a] = b, sz[b] += sz[a];
	}

	int size(int a) { return sz[find(a)]; }
} dsu;

int sub[N];
vector<int> g[N];

int dfs(int u, int p) {
	sub[u] = 1;
	for(int v : g[u]) if(v != p)
		sub[u] += dfs(v, u);
	return sub[u];
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int ida = 1, idb = 2, idc = 3;

	if(a > b) swap(a, b), swap(ida, idb);
	if(a > c) swap(a, c), swap(ida, idc);
	if(b > c) swap(b, c), swap(idb, idc);

	dsu.init();
	for(int i = 0; i < p.size(); i++) if(dsu.find(p[i]) != dsu.find(q[i])) {
		g[p[i]].emplace_back(q[i]);
		g[q[i]].emplace_back(p[i]);
		dsu.unite(p[i], q[i]);	
	}

	int rot = -1;
	function<int(int, int)> find_rot = [&](int u, int p) {
		int mx = n - sub[u];
		for(int v : g[u]) if(v != p)
			mx = max(mx, find_rot(v, u));
		if(mx <= n - b) rot = u;
		return sub[u];
	};

	dfs(0, 0), find_rot(0, 0);
	if(rot == -1) return vector<int>(n);

	//cerr << "rot = " << rot << endl;

	dsu.init();
	for(int i = 0; i < p.size(); i++) {
		if(p[i] == rot || q[i] == rot) continue;
		dsu.unite(p[i], q[i]);
	}

	for(int i = 0; i < p.size(); i++) {
		if(dsu.find(p[i]) == dsu.find(q[i])) continue;
		if(p[i] == rot || q[i] == rot) continue;
		if(dsu.size(p[i]) >= a || dsu.size(q[i]) >= a) continue;

		dsu.unite(p[i], q[i]);
		g[p[i]].emplace_back(q[i]);
		g[q[i]].emplace_back(p[i]);
	}

	vector<int> ans(n);
	
	function<void(int, int, int&, int)> flood = [&](int u, int col, int &cnt, int block) {
		if(ans[u] || cnt == 0 || u == block) return;
		ans[u] = col, --cnt;
		//cerr << "flooding " << u << " " << col << endl;
		for(int v : g[u]) flood(v, col, cnt, block);
	};

	for(int i = 0; i < n; i++) if(i != rot && dsu.size(i) >= a) {
		flood(i, ida, a, rot), flood(rot, idb, b, -1);
		for(int &x: ans) if(!x) x = idc;
		break;
	}

	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < p.size(); i++) if(dsu.find(p[i]) != dsu.find(q[i])) {
      |                 ~~^~~~~~~~~~
split.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~
split.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i < p.size(); i++) {
      |                 ~~^~~~~~~~~~

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