제출 #1222814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222814		toast12	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	19 ms	12732 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;
vector<bool> visited;

void dfs2(int cur, int p, int color) {
    visited[cur] = true;
    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 2: k <= 2
    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++) {
        if (a[i] == a[0]) ans1++, ans2 = 0;
    }
    visited.resize(n);
    for (int i = 1; i < n; i++) {
        if (visited[i]) continue;
        int x = i;
        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);
        f.clear();
    }
    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