Submission #1148382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148382		AbdullahIshfaq	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	548 ms	29636 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int N = 100005;
vector<ll> g[N];
int c[N], dep[N], root[N];
vector<int> colPar,  same, siz[N];
map<int,int> col_at_lev[N];
pair<ll,ll> best = {1,1};
void dfs(int x){
	int cp = colPar[c[x]];
	colPar[c[x]] = x;
	for(auto child : g[x]) {
		dep[child] = dep[x] + 1;
		dfs(child);
	}
	colPar[c[x]] = cp;
	if(cp == -1){
		root[x] = 1;
	}
	else{
		same[cp] += same[x];
	}
}
void dfs2(int x){
	for(auto child : g[x]) {
		dfs2(child);
		if(siz[child].size() > siz[x].size()){
			swap(siz[x], siz[child]);
		}
		for(int i = 0; i < siz[child].size(); i ++){
			siz[x][siz[x].size() - i - 1] += siz[child][siz[child].size() - i - 1];
		}
	}
	siz[x].push_back(1);
	if(!root[x]){
		return;
	}
	int ans = 1;
	for(auto it = col_at_lev[c[x]].upper_bound(dep[x]); it != col_at_lev[c[x]].end(); it++) {
		auto [lev, cnt] = *it;
		int ind = siz[x].size() - (lev - dep[x]) - 1;
		if(ind < 0){
			break;
		}
		ans += min(siz[x][ind], cnt);
	}
	best = max(best, {ans, same[x]});
}
void solve(){
	ll n, k, u;
	cin >> n >> k;
	for(int i = 0; i < n ; i++){
		cin >> c[i];
	}
	for(int i = 1; i < n ; i++){
		cin >> u;
		g[u].push_back(i);
	}
	colPar.resize(n, -1);
	same.resize(n, 1);
	dfs(0);
 	for(int i = 0 ; i < n; i++){
		col_at_lev[c[i]][dep[i]]++;
	}
	dfs2(0);
	cout << best.first << " " << best.first-best.second << endl;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i ++)
		solve();
}

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