Submission #295815

#	Time	Username	Problem	Language	Result	Execution time	Memory
295815		ChrisT	Split the Attractions (IOI19_split)	C++17	100 / 100	215 ms	21144 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
const int MN = 1e5+5;
vector<int> adj[MN];
int sz[MN], ohp[MN], p[MN], togo[MN]; bool vis[MN];
int dfs (int cur) {
	vis[cur] = 1;
	for (int i : adj[cur]) if (!vis[i]) {
		ohp[i] = cur; 
		sz[cur] += dfs(i);
	}
	return ++sz[cur];
}
int getcent (int cur, int tot) {
	for (int i : adj[cur]) if (ohp[i] == cur && sz[i] > (tot >> 1))
		return getcent(i,tot);
	return cur;
}
int calc (int cur) {
	vis[cur] = sz[cur] = 1;
	for (int i : adj[cur]) if ((ohp[i] == cur || ohp[cur] == i) && !vis[i]) {
		p[i] = cur;
		sz[cur] += calc(i);
	}
	return sz[cur];
}
vector<int> find_split (int n, int a, int b, int c, vector<int> P, vector<int> Q) {
	vector<pair<int,int>> vv = {{a,1},{b,2},{c,3}};
	sort(vv.begin(),vv.end());
	vector<int> ret(n,vv[2].second);
	a = vv[0].first; b = vv[1].first; c = vv[2].first;
	for (int i = 0; i < (int)P.size(); i++) {
		adj[++P[i]].push_back(++Q[i]);
		adj[Q[i]].push_back(P[i]);
	}
	auto fillB = [&] (int st, int go, int put) {
		queue<int> q; q.push(st); ret[st-1] = put; --go;
		while (!q.empty()) {
			int cur = q.front(); q.pop();
			for (int i : adj[cur]) if (ret[i-1] == vv[2].second) {
				q.push(i);
				if (go) --go, ret[i-1] = put;
				else return;
			}
		}
	};
	int cent = getcent(1,dfs(1)); memset(vis,0,sizeof vis);
	calc(cent);
	for (int i : adj[cent]) if (p[i] == cent && sz[i] >= a) {
		queue<int> q; q.push(i);
		while (a--) {
			int cur = q.front(); q.pop(); ret[cur-1] = vv[0].second;
			for (int j : adj[cur]) if (p[j] == cur) q.push(j);
		}
		fillB(cent,b,vv[1].second);
		return ret;
	}
	vector<vector<int>> ree; vector<int> cnt,in(n+1);
	for (int i : adj[cent]) if (p[i] == cent) {
		in[i] = (int)ree.size(); ree.push_back({i}); cnt.push_back(sz[i]);
		queue<int> q; q.push(i);
		while (!q.empty()) {
			int cur = q.front(); q.pop(); togo[cur] = i;
			for (int j : adj[cur]) if (p[j] == cur) q.push(j);
		}
	}
	for (int i = 0; i < (int)P.size(); i++) if (p[P[i]] != Q[i] && p[Q[i]] != P[i] && in[P[i]] != in[Q[i]]) {
		int u = in[togo[P[i]]], v = in[togo[Q[i]]];
		if (u == v) continue;
		if (cnt[u] > cnt[v]) swap(u,v);
		cnt[v] += cnt[u];
		for (int j : ree[u]) {in[j] = v; ree[v].push_back(j);}
	}
	for (int i = 0; i < (int)ree.size(); i++) if (cnt[i] >= a) {
		while (cnt[i] - sz[ree[i].back()] >= a) {
			ree[i].pop_back(); cnt[i] -= sz[ree[i].back()];
		} 
		for (int j : ree[i]) {
			queue<int> q; q.push(j);
			while (a && !q.empty()) {
				int cur = q.front(); q.pop(); --a; ret[cur-1] = vv[0].second;
				for (int k : adj[cur]) if (p[k] == cur) q.push(k);
			}
		}
		fillB(cent,b,vv[1].second);
		return ret;
	}
	fill(ret.begin(),ret.end(),0);
	return ret;
}

Compilation message (stderr)

split.cpp: In function 'int calc(int)':
split.cpp:21:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |  vis[cur] = sz[cur] = 1;
      |             ~~~~~~~~^~~

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