Submission #1221008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221008		toast12	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	2584 ms	1114112 KiB

Main

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

vector<int> a, depth;
vector<vector<int>> adj;
vector<vector<int>> freq;

void dfs(int cur, int p) {
    depth[cur] = depth[p]+1;
    freq[depth[cur]][a[cur]]++;
    for (auto e : adj[cur]) {
        if (e != p) dfs(e, cur);
    }
}

pair<int, int> dfs2(int cur, int p, int color) {
    pair<int, int> ret;
    if (a[cur] == color) ret.first++;
    int cnt = 0, children = 0;
    for (auto e : adj[cur]) {
        if (e != p) {
            children++;
            pair<int, int> x = dfs2(e, cur, color);
            ret.first += x.first, ret.second += x.second;
            if (a[e] == color) cnt++;
        }
    }
    freq[depth[cur]+1][color] -= cnt;
    if (cnt == children) return ret;
    if (freq[depth[cur]+1][color] > 0) {
        int temp = min(children-cnt, freq[depth[cur]+1][color]);
        ret.first += temp;
        ret.second += temp;
        freq[depth[cur]+1][color] -= temp;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    a.resize(n+1);
    adj.resize(n+1);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> parent(n);
    parent[0] = -1;
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
        parent[i] = p;
    }
    depth.resize(n+1);
    depth[0] = -1;
    freq.resize(n+1, vector<int>(n+1));
    dfs(0, 0);
    vector<vector<int>> v = freq;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        // make this person the boss
        freq = v;
        pair<int, int> x = dfs2(i, parent[i], a[i]);
        if (x.first > ans1) {
            ans1 = x.first;
            ans2 = x.second;
        }
        else if (x.first == ans1) {
            ans2 = min(ans2, x.second);
        }
    }
    cout << ans1 << ' ' << ans2 << '\n';
    return 0;
}

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