Submission #1122527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122527		Mousa_Aboubaker	Team Coding (EGOI24_teamcoding)	C++20	39 / 100	4096 ms	131808 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <climits>
#include <cmath>
#include <numeric>
#include <string>
#include <bitset>
#include <assert.h>
#include <iomanip>
using namespace std;
 
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
 
const long long infl = 1e18 + 1;
const int inf = 1e9 + 1;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const long double eps = 1e-7;
const int mod = mod1;
 
int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }
int mul(int a, int b) { return (int)((long long)a * b % mod); }
int pwr(int a, int b = mod - 2)
{
	int res = 1;
	for(; b > 0; b >>= 1, a = mul(a, a))
		if(b & 1)
			res = mul(res, a);
	return res;
}
 
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> c(n);
	for(auto &i: c)
		cin >> i;
	vector adj(n, vector<int>());
	for(int i = 1; i < n; i++)
	{
		int u;
		cin >> u;
		adj[u].push_back(i);
	}
	vector<int> dep(n, 0);
	vector up(n, vector<int>(21, -1));
	vector<vector<vector<int>>> children(n, vector<vector<int>>(21, vector<int>()));
	auto dfs1 = [&](auto self, int u, int d) -> void
	{
		dep[u] = d++;
		for(auto i: adj[u])
		{
			children[u][0].push_back(i);
			up[i][0] = u;
			self(self, i, d);
		}
	};
	dfs1(dfs1, 0, 0);
	for(int i = 1; i < 21; i++)
		for(int j = 0; j < n; j++)
		{
			if(~up[j][i - 1])
				up[j][i] = up[up[j][i - 1]][i - 1];
			for(auto x: children[j][i - 1])
				for(auto y: children[x][i - 1])
					children[j][i].push_back(y);
		}
	auto get_kth_par = [&](int x, int k) -> int
	{
		for(int i = 0; i < 21; i++)
			if((k >> i) & 1)
				x = up[x][i];
		return x;
	};
	auto get_kth_child = [&](int x, int k) -> int
	{
		vector<int> b{x};
		for(int i = 0; i < 21; i++)
			if((k >> i) & 1)
			{
				vector<int> c;
				for(auto y: b)
				{
					for(auto z: children[y][i])
					{
						c.push_back(z);
					}
				}
				b = c;
			}
		return (int)b.size();
	};
	vector b(k, vector<int>());
	for(int i = 0; i < n; i++)
	{
		b[c[i]].push_back(i);
	}
	int mx = 0, mn = 0;
	for(auto ar: b)
	{
		int m = (int)ar.size();
		int mxx = inf, idx = 0;
		for(int i = 0; i < m; i++)
			if(dep[ar[i]] < mxx)
				mxx = dep[ar[i]], idx = ar[i];
		map<int, vector<int>> mp;
		vector<int> oo;
		for(int j = 0; j < m; j++)
		{
			if(dep[ar[j]] == dep[idx])
			{
				oo.push_back(ar[j]);
				continue;
			}
			mp[dep[ar[j]]].push_back(ar[j]);
		}
		for(auto o: oo)
		{
			int curr1 = 1, curr2 = 0;
			for(auto [f, s]: mp)
			{
				int mxxx = get_kth_child(o, f - mxx);
				// cout << o << ' ' << mxx << ' ' << f << ' ' << f - mxx << '\n';
				int have = 0;
				int all = (int)s.size();
				for(auto y: s)
					if(get_kth_par(y, f - mxx) == o)
						have++;
				curr2 += min(all - have, mxxx - have);
				curr1 += min(all, mxxx);
			}
			if(curr1 > mx)
			{
				mx = curr1;
				mn = curr2;
			}
			else if(curr1 == mx)
				mn = min(mn, curr2);
		}
	}

	cout << mx << ' ' << mn;
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t = 1;
	// cin >> t;
 
	while (t--) {
		solve();
		cout << (t ? "\n" : "");
	}
}

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