Submission #1191225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191225		ofoz	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	4119 ms	1114112 KiB

Main

#include <bits/stdc++.h>
#define pi pair<int, int>
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) {
    stack<pi> s;
    s.push({v, level});
    while (!s.empty()) {
        tie(v, level) = s.top();
        s.pop();
        vertices[level]++;
        for (int to : adj[v]) {
            s.push({to, level + 1});
        }
    }
    
}

void dfs2(int v, int level, vector<vector<int>>& colorCnt) {
    stack<pi> s;
    s.push({v, level});
    while (!s.empty()) {
        tie(v, level) = s.top();
        s.pop();
        colorCnt[level][col[v]]++;
        for (int to : adj[v]) {
            s.push({to, level + 1});
        }
    }

}

int dfs3(int v, int c) {
    int res = 0;
    if (col[v] == c) res++;
    for (int to : adj[v]) {
        res += dfs3(to, c);
    }
    return res;
}

void dfs(int v, int level, const vector<vector<int>>& colorCnt) {
    int c = col[v];
    vector<int> vertices(n, 0);
    dfs1(v, level, vertices);
    
    int coders = 0, swaps = 0;
    for (int l = level + 1; l < n; l++) {
        coders += min(vertices[l], colorCnt[l][c]);
    }

    swaps = (coders + 1) - dfs3(v, 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: 23 / 23
• Subtask 5: 0 / 19