Submission #1190669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190669		ofoz	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	1479 ms	1114112 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int n, k;
int col[MAXN];
vector<vector<int>> adj;
vector<vector<int>> colorCnt;
pair<int, int> res = {0, 0};

void dfs1(int v, int level, vector<int>& vertices) {
    vertices[level]++;
    for (int to : adj[v]) {
        dfs1(to, level + 1, vertices);
    }
}

void dfs2(int v, int level, vector<vector<int>>& colorCnt) {
    colorCnt[level][col[v]]++;
    for (int to : adj[v]) {
        dfs2(to, level + 1, colorCnt);
    }
}

void dfs(int v, int level, const vector<vector<int>>& colorCnt) {
    int c = col[v];
    vector<int> vertices(n, 0);
    dfs1(v, level, vertices);

    vector<vector<int>> colorCntSubtree(n, vector<int>(k, 0));
    dfs2(v, level, colorCntSubtree);

    int coders = 0, swaps = 0;
    for (int l = level + 1; l < n; ++l) {
        swaps += min(vertices[l] - colorCntSubtree[l][c], colorCnt[l][c] - colorCntSubtree[l][c]);
        coders += min(vertices[l], colorCnt[l][c]);
    }

    if (coders > res.first || (coders == res.first && swaps < res.second)) {
        res = {coders, swaps};
    }

    for (int to : adj[v]) {
        dfs(to, level + 1, colorCnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> col[i];
    }

    adj.assign(n, vector<int>());
    for (int i = 1; i < n; ++i) {
        int x;
        cin >> x;
        adj[x].push_back(i);
    }

    colorCnt.assign(n, vector<int>(k, 0));
    dfs2(0, 0, colorCnt);
    dfs(0, 0, colorCnt);

    cout << res.first + 1 << " " << res.second << "\n";

    return 0;
}

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