Submission #264743

#	Time	Username	Problem	Language	Result	Execution time	Memory
264743		kdh9949	Split the Attractions (IOI19_split)	C++17	100 / 100	221 ms	24696 KiB

split

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

vint solve(int n, int a, int b, vector<vint> &e) {
	vector<vint> te(n);
	vint pn(n), low(n), mlow(n), sz(n), par(n);
	function<void(int, int)> g = [&](int x, int y) {
		static int pc = 0;
		mlow[x] = pn[x] = ++pc;
		sz[x] = 1;
		par[x] = y;
		low[x] = x;

		for(int i : e[x]) {
			if(i == y) continue;
			if(!pn[i]) {
				te[x].push_back(i);
				te[i].push_back(x);
				g(i, x);
				sz[x] += sz[i];
				mlow[x] = min(mlow[x], mlow[i]);
			}
			else {
				if(pn[low[x]] > pn[i]) low[x] = i;
			}
		}
		mlow[x] = min(mlow[x], pn[low[x]]);
	};
	g(0, -1);

	function<int(int, int)> f = [&](int x, int y) {
		for(int i : te[x]) if(i != y && sz[i] >= a) return f(i, x);
		return x;
	};

	int X = f(0, -1);
	for(int &c : te[X]) {
		if(mlow[c] < pn[X] && sz[X] - sz[c] >= a) {
			sz[X] -= sz[c];
			function<int(int, int, int)> rr = [&](int x, int y, int r) {
				if(pn[low[x]] < r) {
					te[x].push_back(low[x]);
					te[low[x]].push_back(x);
					return 1;
				}
				for(int i : te[x]) if(i != y && rr(i, x, r)) return 1;
				return 0;
			};
			rr(c, X, pn[X]);
			for(int &y : te[c]) if(y == X) y = -1;
			c = -1;
		}
	}

	if(n - sz[X] >= a) {
		vint ans(n, 3);
		int cnt;
		function<void(int, int, int)> h = [&](int x, int y, int c) {
			if(cnt) {
				cnt--;
				ans[x] = c;
			}
			for(int i : te[x]) if(i >= 0 && i != y) h(i, x, c);
		};
		int dir = (sz[X] <= n / 2);
		cnt = (dir ? a : b);
		h(X, par[X], 1 + !dir);
		cnt = (dir ? b : a);
		h(par[X], X, 1 + dir);
		return ans;
	}
	else return vint(n, 0);
}

vint find_split(int n, int a, int b, int c, vint p, vint q) {
	vint v = {0, a, b, c};
	vint col = {0, 1, 2, 3};
	sort(all(col), [&](int x, int y){ return v[x] < v[y]; });
	
	vector<vint> e(n);
	for(int i = 0; i < p.size(); i++) {
		e[p[i]].push_back(q[i]);
		e[q[i]].push_back(p[i]);
	}
	
	vint ans = solve(n, v[col[1]], v[col[2]], e);
	for(int &x : ans) x = col[x];
	return ans;
}

Compilation message (stderr)

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

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