Submission #1214965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214965		jhe	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4096 ms	76328 KiB

Main

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

int n, k;
int p[100000], depths[100000], colours[100000];
int jmp[100000][22];
vector<int> child[100000];
vector<int> groups[100000];
map<int,int> depthcnt[100000];
int best, ans;

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

int lca(int a, int b) {
    if (depths[b] < depths[a]) swap(a,b);
    for (int i = 20; i >= 0; i--) if (depths[jmp[b][i]] >= depths[a]) b = jmp[b][i];
    if (b!=a) {
        for (int i = 20; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i];
            b = jmp[b][i];
        }
    }
    if (a!=b) return jmp[a][1];
    else return a;
}

void find(int i) {
    depthcnt[i][depths[i]]++;
    for (int u: child[i]) {
        find(u);
        if (depthcnt[u].size() > depthcnt[i].size()) swap(depthcnt[u],depthcnt[i]);
        for (pair<int,int> j: depthcnt[u]) depthcnt[i][j.first] += j.second;
    }
    map<int,int> m, m2;
    for (int j: groups[colours[i]]) {
        m[depths[j]]++;
        m2[depths[j]] = depthcnt[i][depths[j]];
    }
    int res = 1;
    for (int j: groups[colours[i]]) {
        if (j!=i && lca(j,i) == i) {
            res++;
            m[depths[j]]--;
            m2[depths[j]]--;
        }
    }

    int swapped = 0;
    for (pair<int,int> j: m) if (j.first > depths[i]) swapped += min(j.second, m2[j.first]);

    if (swapped+res > best) {
        best = swapped+res;
        ans = swapped;
    }
    else if (swapped+res == best) {
        if (swapped < ans) ans = swapped;
    }

    // cout << res << " " << swapped << "\n";
    // cout << "\n\n";
    // // cout << i << " " << depths[i] << ":\n";
    // // for (pair<int,int> u: depthcnt[i]) cout << u.first << " " << u.second << "\n";
    // // cout << "\n\n";

}

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

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

    for (int k = 2; k < 21; k++) for (int i = 1; i < n; i++) jmp[i][k] = jmp[jmp[i][k-1]][k-1];

    dfs(0,0);
    find(0);

    cout << best << " " << ans << "\n";
} 

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