Submission #1080364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080364		wiwiho	Team Coding (EGOI24_teamcoding)	C++14	100 / 100	604 ms	127460 KiB

Main

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

#define iter(v) v.begin(), v.end()
#define pb emplace_back
#define ff first
#define ss second
#define SZ(v) int(v.size())

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef zisk
void debug() { cerr << "\n"; }
template<class T, class ... U>
void debug(T a, U... b) {
	cerr << a << " ", debug(b...);
}
template<class T>
void pary(T l, T r){
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, K;
	cin >> n >> K;
	const int B = 400;

	vector<int> color(n);
	vector<vector<int>> pos(K);
	for (int i = 0; i < n; i++) {
		cin >> color[i];
		pos[color[i]].pb(i);
	}

	vector<vector<int>> g(n);
	for (int i = 1; i < n; i++) {
		int p;
		cin >> p;
		g[p].pb(i);
	}

	vector<int> dpt(n), in(n), out(n);
	int ts = 0;
	vector<int> cur(K, -1);
	vector<bool> top(n);
	auto dfs1 = [&](auto dfs, int now) -> void {
		in[now] = ts++;
		if (cur[color[now]] == -1) {
			cur[color[now]] = now;
			top[now] = true;
		}
		for (int i : g[now]) {
			dpt[i] = dpt[now] + 1;
			dfs(dfs, i);
		}
		if (cur[color[now]] == now)
			cur[color[now]] = -1;
		out[now] = ts++;
	};
	dfs1(dfs1, 0);

	auto isAnc = [&](int a, int b) {
		return in[a] <= in[b] && out[b] <= out[a];
	};

	int ans_member = 0, ans_swp = 0;

	auto solve_big = [&](int c) {
		//debug("solve_big", c);
		
		vector<int> total(n + 1);
		for (int i = 0; i < n; i++)
			if (color[i] == c) total[dpt[i]]++;

		vector<int> cnt(n + 1), sz(n + 1);
		auto dfs2 = [&](auto dfs, int now, int type) -> void {
			sz[dpt[now]] += type;
			if (color[now] == c) cnt[dpt[now]] += type;
			for (int i : g[now]) dfs(dfs, i, type);
		};

		for (int i = 0; i < n; i++)
			if (color[i] == c && top[i]) {
				dfs2(dfs2, i, 1);
				int member = 0, swp = 0;
				for (int j = dpt[i]; j <= n && sz[j]; j++) {
					//debug("depth", j, sz[j], cnt[j], total[j]);
					int tmp = min(total[j], sz[j]);
					member += tmp;
					swp += tmp - cnt[j];
				}
				//debug("top", i, member, swp);
				if (member > ans_member) ans_member = member, ans_swp = swp;
				else if (member == ans_member && swp < ans_swp) ans_swp = swp;
				dfs2(dfs2, i, -1);
			}
	};

	for (int i = 0; i < K; i++) 
		if (SZ(pos[i]) > B)
			solve_big(i);

	{
		vector<deque<int>> down(n);
		vector<int> total(n), cnt(n);
		vector<bool> vst(n);
		auto dfs3 = [&](auto dfs, int now) -> void {
			down[now].pb(1);
			for (int i : g[now]) {
				dfs(dfs, i);
				down[i].emplace_front(0);
				if (SZ(down[i]) > SZ(down[now]))
					down[now].swap(down[i]);
				for (int j = 0; j < SZ(down[i]); j++)
					down[now][j] += down[i][j];
			}
			//debug("dfs3", now);
			//pary(iter(down[now]));
			if (SZ(pos[color[now]]) > B) return;
			for (int i : pos[color[now]]) {
				total[dpt[i]]++;
				if (isAnc(now, i)) cnt[dpt[i]]++;
			}
			int member = 0, swp = 0;
			for (int i : pos[color[now]]) {
				int d = dpt[i];
				if (vst[d]) continue;
				vst[d] = true;
				if (d < dpt[now] || d >= dpt[now] + SZ(down[now])) continue;
				int tmp = min(total[d], down[now][d - dpt[now]]);
				member += tmp;
				swp += tmp - cnt[d];
			}
			if (member > ans_member) ans_member = member, ans_swp = swp;
			else if (member == ans_member && swp < ans_swp) ans_swp = swp;
			for (int i : pos[color[now]]) {
				int d = dpt[i];
				total[d] = 0;
				cnt[d] = 0;
				vst[d] = false;
			}
		};
		dfs3(dfs3, 0);
	}

	cout << ans_member << " " << ans_swp << "\n";

}

• Subtask 1: 12 / 12
• Subtask 2: 19 / 19
• Subtask 3: 27 / 27
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19