Submission #1122531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122531		Mousa_Aboubaker	Team Coding (EGOI24_teamcoding)	C++20	19 / 100	3288 ms	34116 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));
	auto dfs1 = [&](auto self, int u, int d) -> void
	{
		dep[u] = d++;
		for(auto i: adj[u])
		{
			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];
	auto get_kth_par = [&](int u, int k) -> int
	{
		for(int i = 0; i < 21; i++)
			if((k >> i) & 1)
				u = up[u][i];
		return u;
	};
	int mx = *max_element(dep.begin(), dep.end());
	vector levels(mx + 1, vector<int>());
	vector whole(mx + 1, vector<int>(2, 0));
	for(int i = 0; i < n; i++)
		levels[dep[i]].push_back(i);
	int cnt1 = 0;
	for(int i = 0; i < n; i++)
	{
		whole[dep[i]][0] += c[i] == c[0];
		whole[dep[i]][1] += c[i] != c[0];
		if(c[i] == c[0])
			cnt1++;
	}
	vector<int> others;
	auto dfs2 = [&](auto self, int u) -> void
	{
		if(c[u] != c[0])
		{
			others.push_back(u);
			return;
		}
		for(auto i: adj[u])
			self(self, i);
	};
	dfs2(dfs2, 0);
	vector<int> mxx(mx + 1, 0), have(mx + 1, 0);
	auto dfs3 = [&](auto self, int u) -> void
	{
		mxx[dep[u]]++;
		if(c[u] != c[0])
		{
			have[dep[u]]++;
		}
		for(auto i: adj[u])
			self(self, i);
	};
	int mxxx = cnt1, mn = 0;
	int curr1 = 0, curr2 = 0;
	for(auto i: others)
	{
		curr1 = 0, curr2 = 0;
		dfs3(dfs3, i);
		for(int j = dep[i]; j <= mx; j++)
		{
			curr2 += min(whole[j][1] - have[j], mxx[j] - have[j]);
			curr1 += min(whole[j][1], mxx[j]);
			have[j] = 0;
			mxx[j] = 0;
		}
		if(curr1 > mxxx)
		{
			mxxx = curr1;
			mn = curr2;
		}
		else if(curr1 == mxxx)
			mn = min(mn, curr2);
	}
	cout << mxxx << ' ' << mn;
	/*
	for(int i = 0; i < n; i++)
	{
		curr1 = 1, curr2 = 0;
		for(int j = dep[i] + 1; j <= mx; j++)
		{
			int all = 0, have = 0, mxx = 0;
			for(auto x: levels[j])
			{
				if(get_kth_par(x, j - dep[i]) == i)
				{
					mxx++;
					if(c[x] == c[i])
					{
						have++;
						all++;
					}
				}
				else if(c[x] == c[i])
				{
					all++;
				}
			}
			curr2 += min(mxx - have, all - have);
			curr1 += min(mxx, all);
		}
		if(curr1 > mxxx)
		{
			mxxx = curr1;
			mn = curr2;
		}
		else if(curr1 == mxxx)
		{
			mn = min(mn, curr2);
		}
	}
	cout << mxxx << ' ' << mn;
	*/
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t = 1;
	// cin >> t;
 
	while (t--) {
		solve();
		cout << (t ? "\n" : "");
	}
}

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