Submission #1080347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080347		wiwiho	Team Coding (EGOI24_teamcoding)	C++14	42 / 100	4097 ms	14364 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

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;

	vector<int> color(n);
	for (int i = 0; i < n; i++) cin >> color[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);
	vector<int> cur(K, -1);
	vector<bool> top(n);
	auto dfs1 = [&](auto dfs, int now) -> void {
		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;
	};
	dfs1(dfs1, 0);

	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++) solve_big(i);

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

}

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