Submission #737185

#	Time	Username	Problem	Language	Result	Execution time	Memory
737185		NeroZein	Split the Attractions (IOI19_split)	C++17	0 / 100	527 ms	1048576 KiB

split

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

vector<int> find_split(int n, int a_, int b_, int c_, vector<int> pp, vector<int> q) {
	vector<int> res(n);
	vector<pair<int,int>> pts = {{a_, 1}, {b_, 2}, {c_, 3}};
	sort(pts.begin(), pts.end()); 
	int m = (int) pp.size();
	vector<vector<int>> g(n); 
	for (int i = 0; i < m; ++i) {
		g[pp[i]].push_back(q[i]);
		g[q[i]].push_back(pp[i]);
	}
	vector<int> pr(n); 
	vector<int> sz(n); 
	function<void(int, int)> Dfs = [&](int v, int p) {
		sz[v] = 1;
		for (int u : g[v]) {
			if (u != p) {
				pr[u] = v;
				Dfs(u, v); 
				sz[v] += sz[u];
			}
		}
	}; 
	Dfs(0, 0); 
	int s; 
	function<void(int, int, int)> color = [&](int v, int p, int c) {
		res[v] = c;
		--s;
		for (int u : g[v]) {
			if (!s) return; 
			if (u == p) continue; 
			color(u, v, c);
		}
	};
	bool f = false;
	for (int i = 0; i < n; ++i) {
		if (sz[i] >= pts[0].first && n - sz[i] >= pts[1].first) {
			s = pts[0].first;
			color(i, pr[i], pts[0].second);
			s = pts[1].first;
			color(pr[i], i, pts[1].second); 
			for (int j = 0; j < n; ++j) {
				if (!res[j]) {
					res[j] = pts[2].second; 
				}
			}
			f = true; 
			break; 
		}
	}
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:38:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   38 |  bool f = false;
      |       ^

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