Submission #1063144

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

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 25;
vector <int> adj[MAXN];
int sze[MAXN], p[MAXN];
bool vis[MAXN];
void dfs (int pos, int par) {
	sze[pos] = 1; p[pos] = par;
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs(j, pos);
			sze[pos] += sze[j];
		}
	}
}
vector <int> ret;
int tt;
void dfs2 (int pos, int par, int d) {
	assert(!vis[pos]); vis[pos] = 1;
	if (tt >= 1) {
		//assert(ret[pos] == 0);
		ret[pos] = d;
	}
	tt--;
	for (auto j : adj[pos]) {
		if (j != par) {
			dfs2(j, pos, d);
		}
	}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector <int> d = {1, 2, 3};
	if (a > b) {
		swap(a, b); swap(d[0], d[1]);
	}
	if (a > c) {
		swap(a, c); swap(d[0], d[2]);
	}
	if (b > c) {
		swap(b, c); swap(d[1], d[2]);
	}
	for (int i = 0; i < (int)p.size(); i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	ret.resize(n); for (auto &i : ret) i = 0;
	dfs(0, -1);
	for (int i = 1; i < n; i++) {
		if (sze[i] >= a && n - sze[i] >= b) {
			tt = a; dfs2(i, p[i], d[0]);
			int cnt1 = 0, cnt2 = 0;
			for (int j = 0; j < n; j++) {
				cnt1 += ret[j] == d[0];
			}
			assert(cnt1 == a);
			tt = b; dfs2(p[i], i, d[1]);
			cnt1 = 0, cnt2 = 0;
/*			for (int j = 0; j < n; j++) {
				cnt1 += ret[j] == d[0];
				cnt2 += ret[j] == d[1];
			}
			assert(cnt1 == a); assert(cnt2 == b);*/
			for (int j = 0; j < n; j++) {
				if (ret[j] == 0) {
					ret[j] = d[2];
				}
			}
			return ret;
		}
		if (sze[i] >= b && n - sze[i] >= a) {
			tt = b; dfs2(i, p[i], d[1]);
			int cnt1 = 0, cnt2 = 0;
			for (int j = 0; j < n; j++) {
				cnt1 += ret[j] == d[1];
			}
			assert(cnt1 == b);
			tt = a; dfs2(p[i], i, d[0]);
			cnt1 = 0, cnt2 = 0;
/*			for (int j = 0; j < n; j++) {
				cnt1 += ret[j] == d[1];
				cnt2 += ret[j] == d[0];
			}
			assert(cnt1 == b); assert(cnt2 == a);*/
			for (int j = 0; j < n; j++) {
				if (ret[j] == 0) {
					ret[j] = d[2];
				}
			}
			return ret;
		}
	}
	return ret;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:52:18: warning: variable 'cnt2' set but not used [-Wunused-but-set-variable]
   52 |    int cnt1 = 0, cnt2 = 0;
      |                  ^~~~
split.cpp:73:18: warning: variable 'cnt2' set but not used [-Wunused-but-set-variable]
   73 |    int cnt1 = 0, cnt2 = 0;
      |                  ^~~~

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