Submission #1148362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148362		Jawad_Akbar_JJ	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	62 ms	35772 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
vector<int> nei[N], cols[N], Ver[N], lev[N];
vector<pair<int,int>> Vec, vc;
int st[N], en[N], alr[N], Seen[N], cnt[N], cur, a[N];

int dfs(int u, int p, int h, int sz = 1){
	st[u] = cur++;
	cols[h].push_back(a[u]);
	Ver[h].push_back(st[u]);

	Vec.push_back({h, a[u]});
	alr[u] = cnt[a[u]]++;
	Seen[a[u]]++;

	for (int i : nei[u]){
		if (i == p) continue;
		sz += dfs(i, u, h + 1);
	}
	alr[u] = cnt[a[u]] - alr[u];

	en[u] = cur++;

	if (Seen[a[u]] == 1)
		vc.push_back({-sz, u});
	Seen[a[u]]--;
	return sz;
}

int check(int rt, int ans = 0){
	for (int i : lev[a[rt]]){
		int m1 = upper_bound(begin(cols[i]), end(cols[i]), a[rt]) - upper_bound(begin(cols[i]), end(cols[i]), a[rt] - 1);
		int m2 = upper_bound(begin(Ver[i]), end(Ver[i]), en[rt]) - upper_bound(begin(Ver[i]), end(Ver[i]), st[rt] - 1);
		ans += min(m1, m2);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k, p, Ans1 = 0, Ans2, cnst = 0;
	cin>>n>>k;

	for (int i=1;i<=n;i++)
		cin>>a[i];

	for (int i=2;i<=n;i++){
		cin>>p;
		nei[p + 1].push_back(i);
	}

	dfs(1, 1, 1);
	sort(begin(Vec), end(Vec));

	for (int i=1;i<=n;i++){
		sort(begin(Ver[i]), end(Ver[i]));
		sort(begin(cols[i]), end(cols[i]));
	}

	for (auto [i, j] : Vec){
		if (lev[j].size() == 0 or lev[j].back() != i)
			lev[j].push_back(i);
	}
	sort(begin(vc), end(vc));

	for (auto [j, i] : vc){
		if (-j < Ans1 or cnt[a[i]] < Ans1) continue;
		int ret = check(i);
		if (ret > Ans1)
			Ans1 = ret, Ans2 = ret - alr[i];
		else if (ret == Ans1)
			Ans2 = min(Ans2, ret - alr[i]);
	}
	cout<<Ans1<<" "<<Ans2<<'\n';
}

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