Submission #1214933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214933		jhe	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	4093 ms	9596 KiB

Main

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

int n, k;
int p[100000], depths[100000], colours[100000];
vector<int> child[100000];
int freq[2001], bigfreq[2001];
int cnt;

void dfs(int i, int depth) {
    depths[i] = depth;
    for (int u: child[i]) dfs(u,depth+1);
}

void in(int i, int colour) {
    if (colours[i] == colour) cnt++;
    else freq[depths[i]]++;
    for (int u: child[i]) in(u,colour);
}

void out(int i, int colour, int lead) {
    if (i==lead) return;
    if (colours[i] == colour) bigfreq[depths[i]]++;
    for (int u: child[i]) out(u,colour,lead);
}

signed main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> colours[i];

    for (int i = 1; i < n; i++) {
        cin >> p[i];
        child[p[i]].push_back(i);
    }

    dfs(0,0);
    
    int best = 0, ans;
    for (int i = 0; i < n; i++) {
        cnt = 0;
        for (int j = 0; j < n; j++) freq[j] = bigfreq[j] = 0;
        in(i,colours[i]);
        out(0,colours[i],i);

        int swapped = 0;
        
        for (int j = depths[i]+1; j < n; j++) swapped += min(bigfreq[j], freq[j]);

        if (best == cnt+swapped) ans = min(ans, swapped);
        else if (cnt+swapped > best) {
            best = cnt+swapped;
            ans = swapped;
        }
    }
    cout << best << " " << ans << "\n";
} 

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