Submission #1221024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221024		toast12	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	4094 ms	1114112 KiB

Main

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

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

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

vector<pair<int, int>> f;

void dfs2(int cur, int p, int color) {
    f[depth[cur]].first += (a[cur] == color ? 1 : 0);
    f[depth[cur]].second++;
    for (auto e : adj[cur]) dfs2(e, cur, color);
}

int main() {
    // subtask 4: n <= 2000
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    adj.resize(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    depth.resize(n);
    depth[0] = -1;
    freq.resize(k, vector<int>(n));
    dfs(0, 0);
    int ans1 = 0, ans2 = INT_MAX;
    for (int i = 0; i < n; i++) {
        f.resize(n);
        dfs2(i, i, a[i]);
        int cnt = 0, swaps = 0;
        for (int j = 0; j < n; j++) {
            cnt += f[j].first;
            if (freq[a[i]][j] > f[j].first) {
                int temp = min(freq[a[i]][j]-f[j].first, f[j].second-f[j].first);
                cnt += temp;
                swaps += temp;
            }
        }
        f.clear();
        if (cnt > ans1) {
            ans1 = cnt;
            ans2 = swaps;
        }
        else if (cnt == ans1) ans2 = min(ans2, swaps);
    }
    cout << ans1 << ' ' << ans2 << '\n';
    return 0;
}

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