Submission #1145374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145374		monkey133	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	2152 ms	1114112 KiB

Main

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll const blk = 100000000;

ll n, k, label = 0;
ll color[100005], par[100005], in[100005], out[100005], cnt[100005], dep[100005], big[100005];
vector<ll> adj[100005], nodelist[100005];
unordered_map<ll, ll> dp[100005], dp2[100005], dp3[100005], dp4[100005], dp5[100005], col[100005];
unordered_set<ll> deplist[100005];
pi ans = mp(-1e15, -1e15);


void precomp1(ll x = 0)
{
	in[x] = ++label;
	for (ll u: adj[x]) 
	{
		dep[u] = dep[x] + 1;
		precomp1(u);
	}
	out[x] = label;
	if (!big[x]) deplist[color[x]].insert(dep[x]);
}

void precomp2(ll x = 0)
{
	col[color[x]][dep[x]]++;
	for (ll u: adj[x]) 
	{
		precomp2(u);
		if (dp[x].size() < dp[u].size()) swap(dp[u], dp[x]);
		for (pi u: dp[u]) dp[x][u.f] += u.s;
	}
	dp[x][dep[x]]++;
	for (ll u: deplist[color[x]]) dp2[x][u] += dp[x][u];
}


void dfs(ll x, ll c, ll yes = 1)
{
	//show2(x, yes);
	for (ll u: adj[x]) 
	{
		dfs(u, c, yes&ll(color[x]!=c));
		if (dp4[x].size() < dp4[u].size()) swap(dp4[u], dp4[x]);
		for (pi v: dp4[u]) dp4[x][v.f] += v.s;
		if (dp5[x].size() < dp5[u].size()) swap(dp5[u], dp5[x]);
		for (pi v: dp5[u]) dp5[x][v.f] += v.s;
		
	}
	if (yes && color[x]==c)
	{
		//show(x);
		ll res = 0, res2 = 0;
		for (ll u: deplist[c])
		{
			if (u <= dep[x]) continue;
			//show3(u, dp4[x][u], col[c][u]);
			ll take = min(dp4[x][u], col[c][u]);
			res += take;
			res2 +=  take - dp5[x][u];
		}
		//show2(res, res2);
		ans = max(ans, mp(res, -res2));
	}
	dp4[x][dep[x]]++;
	if (c==color[x]) dp5[x][dep[x]]++;
}

void solve(ll c)
{
	//for (ll u: nodelist[c]) show(u);
	for (ll i=0; i<nodelist[c].size(); ++i)
	{
		for (ll j=i + 1; j<nodelist[c].size(); ++j)
		{
			ll x = nodelist[c][i], y = nodelist[c][j];
			if (in[x] > in[y]) swap(x, y);
			if (in[x] <= in[y] && in[y] <= out[x]) dp3[x][dep[y]]++;
		}
	}
	for (ll i=0; i<nodelist[c].size(); ++i)
	{
		ll res = 0, res2 = 0, x = nodelist[c][i];
		//show(x);
		for (ll u: deplist[c])
		{
			if (u <= dep[x]) continue;
			//show(u);
			ll take = min(dp2[x][u], col[c][u]);
			res += take;
			res2 += max(0LL, take - dp3[x][u]);
		}
		ans = max(ans, mp(res, -res2));
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	for (ll i=0; i<n; ++i) {cin >> color[i]; cnt[color[i]]++; nodelist[color[i]].pb(i); }
	for (ll i=0; i<k; ++i) if (cnt[i] > blk) big[i] = 1;
	for (ll i=1; i<n; ++i) {cin >> par[i];  adj[par[i]].pb(i);}
	precomp1(); precomp2();
	for (ll i=0; i<k; ++i)
	{
		//show("start");
		//show(i);
		if (big[i]) 
		{
			for (ll j=0; j<n; ++j) {dp5[j].clear(); dp4[j].clear();}
			dfs(0, i, 1);
		}
		else {solve(i);}
	}
	cout << ans.f + 1 << ' ' << -ans.s << endl;
	return 0;
}

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