Submission #1274948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274948		Robert_junior	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	4133 ms	1068832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back  
#define all(x) x.begin(), x.end()
#define ins insert
#define F first
#define S second
const int N = 4e5 + 7, mod = 998244353;
vector<int>g[N];
int tin[N], tout[N], eul[N], timer, d[N], c[N];
map<int, int>mp[N];
void dfs(int v, int p){
    tin[v] = ++timer;
    mp[d[v]][c[v]]++;
    eul[tin[v]] = v;
    for(auto to : g[v]){
        if(to == p) continue;
        d[to] = d[v] + 1;  
        dfs(to, v);
    }
    tout[v] = timer;
}
void solve(){
	int n, k;
	cin>>n>>k;
	for(int i = 1; i <= n; i++){
	    cin>>c[i];
	}
	for(int i = 2; i <= n; i++){
	    int u;
	    cin>>u;
	    u++;
	    g[u].pb(i);
	    g[i].pb(u);
	}
	dfs(1, 1);
	pair<int, int>ans = {0, 0};
	for(int i = 1; i <= n; i++){
	    map<int, int>cnt;
	    int cur = 0;
	    for(int j = tin[i]; j <= tout[i]; j++){
	        cnt[d[eul[j]]]++;
	        if(c[eul[j]] == c[i]) cur++;
	    }
	    int sum = 0;
	    for(auto it : cnt){
	        sum += min(mp[it.F][c[i]], it.S);
	    }
	    cur = sum - cur;
	    if(sum > ans.F){
	        ans = {sum, cur};
	    }
	    else if(sum == ans.F){
	        ans.S = max(ans.S, cur);
	    }
	}
	cout<<ans.F<<' '<<ans.S<<'\n';
}
signed main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
    //freopen("pieaters.in", "r", stdin);
    //freopen("pieaters.out", "w", stdout);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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