Submission #823896

#	Time	Username	Problem	Language	Result	Execution time	Memory
823896		Blagoj	Split the Attractions (IOI19_split)	C++17	100 / 100	96 ms	29968 KiB

split

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

using namespace std;

const int N = 1e5 + 5;

int tin[N], low[N], timer = 0, mark[N], sz[N], A, B, C, n;
bool special[N];

vector<int> g[N], children[N];

bool found = 0;

void color1(int cur, int type, int &Left) {
    if (Left == 0) mark[cur] = 3;
    else {
		mark[cur] = type;
    	Left--;
	}
	for (auto next : children[cur]) color1(next, type, Left);
}

void color2(int cur, int type, int &Left) {
	if (Left == 0) mark[cur] = 3;
    else {
		mark[cur] = type;
    	Left--;
	}
	for (auto next : g[cur]) if (mark[next] == 0) color2(next, type, Left);
}

void dfs(int cur) {
	tin[cur] = low[cur] = ++timer;
	sz[cur] = 1;
	for (auto next : g[cur]) {
		if (tin[next] == 0) {
			dfs(next);
			children[cur].push_back(next);
			sz[cur] += sz[next];
			low[cur] = min(low[cur], low[next]);
		}
		else low[cur] = min(low[cur], tin[next]);
	}
	if (found) return;
	if (sz[cur] >= A) {
		int sum = sz[cur];
		for (auto next : children[cur]) {
			if (low[next] < tin[cur] && sum - sz[next] >= A) {
				sum -= sz[next];
				special[next] = 1;
			}
		}
		if (sum >= A && n - sum >= B) {
			found = 1;
			mark[cur] = 1;
			int Left = A - 1;
			for (auto next : children[cur]) {
				if (!special[next]) color1(next, 1, Left);
			}
			color2(0, 2, B);
		}
		else if (sum >= B && n - sum >= A) {
			found = 1;
			mark[cur] = 2;
			int Left = B - 1;
			for (auto next : children[cur]) {
				if (!special[next]) color1(next, 2, Left);
			}
			color2(0, 1, A);
		}
	}
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	n = _n;
	vector<pair<int, int>> srt = {{-1, 0}, {a, 1}, {b, 2}, {c, 3}};
	sort(srt.begin(), srt.end());
	A = srt[1].first;
	B = srt[2].first;
	C = srt[3].first;
	for (int i = 0; i < p.size(); i++) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	dfs(0);
	vector<int> ans(n);
	for (int i = 0; i < n; i++) ans[i] = srt[mark[i]].second;
	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:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  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