Submission #1221098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221098		overwatch9	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	36 ms	8644 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 1;
vector <int> adj[maxn];
int grps[maxn][maxn];
int col[maxn];
int depth[maxn];
void dfs(int s, int d) {
    depth[s] = d;
    grps[d][col[s]]++;
    for (auto i : adj[s])   
        dfs(i, d+1);
}
pair <int, int> get_best(pair <int, int> a, pair <int, int> b) {
    if (a.first > b.first)
        return a;
    if (b.first > a.first)
        return b;
    if (a.second < b.second)
        return a;
    return b;
}
vector <pair <int, int>> f;
void dfs2(int s, int c) {
    if (col[s] == c)
        f[depth[s]].first++;
    f[depth[s]+1].second += (int)adj[s].size();
    for (auto i : adj[s])
        dfs2(i, c);
}
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> col[i];
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    dfs(0, 0);
    pair <int, int> ans = {0, 0};
    for (int i = 0; i < n; i++) {
        // set i as the head
        f.clear();
        f.resize(n+2);
        dfs2(i, col[i]);
        pair <int, int> tp = {1, 0};
        for (int d = depth[i]+1; d < n; d++) {
            tp.first += f[d].first;
            if (grps[d][col[i]] > f[d].first) {
                int extra = min(grps[d][col[i]] - f[d].first, f[d].second - f[d].first);
                tp.first += extra;
                tp.second += extra;
            }
        }
        ans = get_best(ans, tp);
    }
    cout << ans.first << ' ' << ans.second << '\n';
}

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