Submission #1189788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189788		Nomio	Team Coding (EGOI24_teamcoding)	C++20	35 / 100	4091 ms	1114112 KiB

Main

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

const int maxn = 1e5 + 5;
using ll = long long;

vector<int> adj[maxn], dis(maxn, 1e6), a(maxn), c(maxn), b(maxn), in(maxn), out(maxn), lvl[maxn];
int H = 0;

int timer = -1;

void euler(int u) {
	timer++;
	in[u] = timer;
	a[timer] = u;
	lvl[dis[u]].push_back(in[u]);
	for(int v : adj[u]) {
		dis[v] = dis[u] + 1;
		H = max(H, dis[v]);
		euler(v);
	} 
	out[u] = timer;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	bool w = 1;
	for(int i = 0; i < n; i++) {
		cin >> c[i];
	}
	for(int i = 1; i < n; i++) {
		cin >> b[i];
		adj[b[i]].push_back(i);
		if(b[i] != i - 1) w = 0;
	}
	if(w) {
		int mx = 0;
		int cnt[k + 1] {};
		for(int i = n - 1; i >= 0; i--) {
			cnt[c[i]]++;
			mx = max(mx, cnt[c[i]]);
		}
		cout << mx << ' ' << 0 << '\n';
	} else {
		dis[0] = 0;
		lvl[0].push_back(0);
		euler(0);
		vector<int> cnt[H + 1][k + 1];
		for(int i = 1; i <= H; i++) {
			for(int x : lvl[i]) {
				cnt[i][c[a[x]]].push_back(x);
			}
		}
		int mx = 1, sw = 0;
		for(int i = 0; i < n; i++) {
			int l = dis[i];
			int mxx = 1, swp = 0;
			for(int j = l + 1; j <= H; j++) {
				int x = lower_bound(lvl[j].begin(), lvl[j].end(), in[i]) - lvl[j].begin();
				int y = upper_bound(lvl[j].begin(), lvl[j].end(), out[i]) - lvl[j].begin() - 1;
				int mn = min((int)cnt[j][c[i]].size(), y - x + 1);
				x = lower_bound(cnt[j][c[i]].begin(), cnt[j][c[i]].end(), in[i]) - cnt[j][c[i]].begin();
				y = upper_bound(cnt[j][c[i]].begin(), cnt[j][c[i]].end(), out[i]) - cnt[j][c[i]].begin() - 1;
				mxx += mn;
				swp += (mn - (y - x + 1));
			}
			if(mxx > mx) {
				mx = mxx;
				sw = swp;
			} else if(mxx == mx) sw = min(sw, swp);
		}
		cout << mx << ' ' << sw << '\n';
	} 
	return 0;
}

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