Submission #1189957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189957		Nomio	Team Coding (EGOI24_teamcoding)	C++20	62 / 100	4097 ms	37624 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], nadj[maxn * 2 + 1], v[maxn];
vector<int> par(maxn, -1), vec;
int H = 0;
int timer = -1;
int n, k;

void euler(int u) {
	timer++;
	in[u] = timer;
	a[timer] = u;
	if(v[c[u]].empty()) {
		nadj[n + c[u]].push_back(u);
		par[u] = n + c[u];
	} else {
		nadj[v[c[u]].back()].push_back(u);
		par[u] = v[c[u]].back();
	} 
	v[c[u]].push_back(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);
	} 
	v[c[u]].pop_back();
	out[u] = timer;
}

void dfs(int u) {
	for(int v : nadj[u]) {
		vec.push_back(dis[v]);
		dfs(v);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	bool w = 1;
	int mx = 1, sw = 0;
	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];
		map<pair<int, int>, vector<int>> cnt;
		for(int i = 1; i <= H; i++) {
			for(int x : lvl[i]) {
				cnt[{i, c[a[x]]}].push_back(x);
			}
		}
//		for(int i = 0; i < n + k; i++) {
//			cout << i << " : ";
//			for(int x : nadj[i]) {
//				cout << x << ' ';
//			}
//			cout << '\n';
//		}
		for(int i = 0; i < k; i++) {
			vec.clear();
//			cout << i + n << ' ' << "ok" << '\n';
			dfs(n + i);
			sort(vec.begin(), vec.end());
			vec.erase(unique(vec.begin(), vec.end()), vec.end());
//			for(int x : vec) cout << x << ' ';
//			cout << '\n';
			for(int x : nadj[n + i]) {
				int mxx = 1, swp = 0;
				for(int h : vec) {
					if(h <= dis[x]) continue;
					int l = lower_bound(lvl[h].begin(), lvl[h].end(), in[x]) - lvl[h].begin();
					int r = upper_bound(lvl[h].begin(), lvl[h].end(), out[x]) - lvl[h].begin() - 1;
					int mn = min((int)cnt[{h, c[x]}].size(), r - l + 1);
					l = lower_bound(cnt[{h, c[x]}].begin(), cnt[{h, c[x]}].end(), in[x]) - cnt[{h, c[x]}].begin();
					r = upper_bound(cnt[{h, c[x]}].begin(), cnt[{h, c[x]}].end(), out[x]) - cnt[{h, c[x]}].begin() - 1;
					mxx += mn;
					swp += (mn - (r - l + 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: 27 / 27
• Subtask 4: 23 / 23
• Subtask 5: 0 / 19