Submission #420835

#	Time	Username	Problem	Language	Result	Execution time	Memory
420835		QCFium	Split the Attractions (IOI19_split)	C++14	33 / 100	105 ms	12868 KiB

split

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

static std::vector<std::vector<int> > hen;
static std::vector<int> size;
static std::vector<int> par;

void dfs(int i, int prev) {
	par[i] = prev;
	for (auto j : hen[i]) if (j != prev) {
		dfs(j, i);
		size[i] += size[j];
	}
}

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
	hen.resize(n);
	for (int i = 0; i < (int) p.size(); i++) {
		hen[p[i]].push_back(q[i]);
		hen[q[i]].push_back(p[i]);
	}
	std::vector<int> res(n, -1);
	
	auto bfs = [&] (int i, int num, int ban) {
		std::vector<bool> visited(n);
		std::queue<int> que;
		que.push(i);
		visited[i] = true;
		std::vector<int> group;
		while (que.size()) {
			auto i = que.front();
			que.pop();
			group.push_back(i);
			if ((int) group.size() == num) break;
			for (auto j : hen[i]) if (j != ban && res[j] == -1 && !visited[j]) visited[j] = true, que.push(j);
		}
		return group;
	};
	
	if ((int) p.size() == n - 1) {
		size.assign(n, 1);
		par.resize(n);
		dfs(0, -1);
		for (int i = 1; i < n; i++) {
			if (a <= size[i] && b <= n - size[i]) {
				for (auto j : bfs(i, a, par[i])) res[j] = 1;
				for (auto j : bfs(par[i], b, i)) res[j] = 2;
				for (auto &j : res) if (j == -1) j = 3;
				break;
			}
			if (a <= size[i] && c <= n - size[i]) {
				for (auto j : bfs(i, a, par[i])) res[j] = 1;
				for (auto j : bfs(par[i], c, i)) res[j] = 3;
				for (auto &j : res) if (j == -1) j = 2;
				break;
			}
			if (b <= size[i] && c <= n - size[i]) {
				for (auto j : bfs(i, b, par[i])) res[j] = 2;
				for (auto j : bfs(par[i], c, i)) res[j] = 3;
				for (auto &j : res) if (j == -1) j = 1;
				break;
			}
			if (b <= size[i] && a <= n - size[i]) {
				for (auto j : bfs(i, b, par[i])) res[j] = 2;
				for (auto j : bfs(par[i], a, i)) res[j] = 1;
				for (auto &j : res) if (j == -1) j = 3;
				break;
			}
			if (c <= size[i] && a <= n - size[i]) {
				for (auto j : bfs(i, c, par[i])) res[j] = 3;
				for (auto j : bfs(par[i], a, i)) res[j] = 1;
				for (auto &j : res) if (j == -1) j = 2;
				break;
			}
			if (c <= size[i] && b <= n - size[i]) {
				for (auto j : bfs(i, c, par[i])) res[j] = 3;
				for (auto j : bfs(par[i], b, i)) res[j] = 2;
				for (auto &j : res) if (j == -1) j = 1;
				break;
			}
		}
		if (res[0] == -1) res.assign(n, 0);
	} else if (a == 1) {
		auto group2 = bfs(0, b, -1);
		for (auto i : group2) res[i] = 2;
		*std::find(res.begin(), res.end(), -1) = 1;
		for (auto &i : res) if (i == -1) i = 3;
	} else assert(0);
	return res;
}

#ifdef LOCAL
int main() {
	int n = ri();
	int m = ri();
	int a = ri();
	int b = ri();
	int c = ri();
	std::vector<int> p(m);
	std::vector<int> q(m);
	for (int i = 0; i < m; i++) {
		p[i] = ri();
		q[i] = ri();
	}
	auto res = find_split(n, a, b, c, p, q);
	for (auto i : res) std::cerr << i << " ";
	std::cerr << std::endl;
	
	
	return 0;
}
#endif

Compilation message (stderr)

split.cpp: In function 'int ri()':
split.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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