Submission #1171733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171733		nguyenkhangninh99	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	367 ms	42816 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 3e5 + 9;
const int blocksz = 320;

int n, k, c[N];
int h[N], sz[N];
int max_depth = 0;
int in[N], out[N], timedfs = 0;
int tour[N];

vector <int> adj[N];
vector <int> pos[N];
vector <int> large, small;

int mark[N];

pp res = {1LL, 0LL};

pp cmp (pp A, pp B){
	if (A.fi > B.fi) return A;
	if (A.fi < B.fi) return B;
	if (A.se <= B.se) return A;
	return B;
}

void dfs (int u){
	tour[++timedfs] = u;
	in[u] = timedfs;
	max_depth = max (max_depth, h[u]);
	for (int v : adj[u]){
		h[v] = h[u] + 1;
		dfs (v);
	}
	out[u] = timedfs;
}

int cur_color; 
int cnt_color[N];
int num[N];
int cnt[N];

void dfs_color (int u){
	if (c[u] == cur_color){
		cnt_color[h[u]]++;
		cnt[u]++;
	}
	for (int v : adj[u]){
		dfs_color (v);
		cnt[u] += cnt[v];
	}
}

int mp[N];

pp temp_ans;

void dfs4 (int u){
	if (mp[h[u]] < cnt_color[h[u]]) temp_ans.fi++;
	mp[h[u]]++;
	for (int v : adj[u]) dfs4 (v);
}

void dfs3 (int u){
	if (c[u] == cur_color){
		temp_ans.fi = 0;
		dfs4 (u);
		temp_ans.se = cnt[u] - temp_ans.fi;
		temp_ans.se = -temp_ans.se;
		res = cmp (res, temp_ans);
		for (int i = h[u]; i <= max_depth; i++) mp[i] = 0;
		return;
	}
	for (int v : adj[u]) dfs3 (v);
}

void solve_large (int color){
	cur_color = color;
	memset (cnt, 0, sizeof (cnt));
	memset (cnt_color, 0, sizeof (cnt_color));
	dfs_color (1);
	dfs3 (1);
}

vector <int> L[N];

void dfs_merge (int u){
	if (adj[u].size () == 0){
		pos[u].push_back (1);
		return;
	}
	for (int v : adj[u]){
		dfs_merge (v);
		if (pos[v].size () > pos[u].size ()) swap (pos[u], pos[v]);
		for (int z = 0; z < pos[v].size (); z++){
			if (z >= pos[u].size ()) pos[u].push_back (0);
			pos[u][z] += pos[v][z];
		}
		pos[v].clear ();
	}
	pos[u].insert (pos[u].begin (), 1);
	temp_ans.fi = temp_ans.se = 0;
	for (int i = 0; i < L[c[u]].size (); i++){
		int x = L[c[u]][i];
		if (h[x] < h[u]) continue;
		int cnt_node = 1;
		int in_subtree = 0;
		int j = i + 1;
		if (in[u] <= in[x] && in[x] <= out[u]) in_subtree = 1;
		while (j < L[c[u]].size () && h[L[c[u]][j]] == h[x]){
			cnt_node++;
			int y = L[c[u]][j];
			if (in[u] <= in[y] && in[y] <= out[u]) in_subtree++;
			j++;
			if (j >= L[c[u]].size ()) break;
		}
		if (h[x] - h[u] < pos[u].size () && h[x] - h[u] >= 0){
			temp_ans.fi += min (cnt_node, pos[u][h[x] - h[u]]);
			temp_ans.se += min (cnt_node, pos[u][h[x] - h[u]]) - in_subtree;
		}
		i = j - 1;
	}
	res = cmp (res, temp_ans);
}

bool cmp_depth (int u, int v){
	return h[u] < h[v];
}

void solve_small (){
	for (int i = 1; i <= n; i++){
		if (mark[c[i]] == 0) continue;
		L[c[i]].push_back (i);
	}
	for (int i = 0; i < k; i++) if (L[i].size ()) sort (L[i].begin (), L[i].end (), cmp_depth);
	dfs_merge (1);
}

signed main (){
	ios_base::sync_with_stdio (false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> c[i]; 
        sz[c[i]]++;
	}
	for (int i = 0; i < k; i++){
		if (sz[i] >= blocksz) large.push_back (i);
		else if (sz[i]){
			small.push_back (i);
			mark[i]++;
		}
	}
	for (int i = 2, p; i <= n; i++){
		cin >> p; p++;
		adj[p].push_back (i);
	}
	dfs (1);
	for (int i : large) solve_large (i);
	solve_small ();
	cout << res.fi << ' ' << res.se;
}

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