Submission #1222832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222832		toast12	Team Coding (EGOI24_teamcoding)	C++20	19 / 100	3398 ms	1114112 KiB

Main

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

const int MAXN = 2e5;
const int MAXK = 2;

int a[MAXN+1], depth[MAXN+1];
vector<int> adj[MAXN+1];
int freq[MAXK][MAXN];

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);
}

vector<int> v;

void dfs3(int cur, int p) {
    if (a[cur] != a[0]) {
        v.push_back(cur);
        return;
    }
    for (auto e : adj[cur]) dfs3(e, cur);
}

int main() {
    // subtask 2: k <= 2
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    depth[0] = -1;
    dfs(0, 0);
    int ans1 = 0, ans2 = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (a[i] == a[0]) ans1++, ans2 = 0;
    }
    dfs3(0, 0);
    for (auto x : v) {
        f.clear();
        f.resize(n);
        dfs2(x, x, a[x]);
        int cnt = 1, swaps = 0;
        for (int j = depth[x]+1; j < n; j++) {
            if (f[j].second == 0) break;
            cnt += f[j].first;
            if (freq[a[x]][j] > f[j].first) {
                int temp = min(freq[a[x]][j]-f[j].first, f[j].second-f[j].first);
                cnt += temp;
                swaps += temp;
            }
        }
        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: 19 / 19
• Subtask 3: 0 / 27
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19