Submission #1098640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098640		Trisanu_Das	Team Coding (EGOI24_teamcoding)	C++17	19 / 100	71 ms	30424 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    cin >> n >> k;

    vector<ll> col(n);
    vector<vector<ll>> adj(n);
    vector<ll> depth(n);
    vector<ll> team(n, -1);

    pair<ll, ll> res = {0, 0};

    for (int i = 0; i < n; ++i) {
        cin >> col[i];
        if (col[i] == col[0]) res.first++;
    }

    for (int i = 0; i < n - 1; ++i) {
        ll p;
        cin >> p;
        adj[p].push_back(i + 1);
    }

    queue<ll> q;
    q.push(0);
    depth[0] = 0;
    ll t = 0;

    while (!q.empty()) {
        ll curr = q.front();
        q.pop();
        for (ll v : adj[curr]) {
            depth[v] = depth[curr] + 1;
            if (team[curr] == -1 && col[v] != col[0]) team[v] = t++;
            else team[v] = team[curr];
            q.push(v);
        }
    }

    vector<ll> numPerLayer(n, 0);
    vector<map<ll, ll>> vPerTeamPerLayer(t);
    vector<map<ll, ll>> vColPerTeamPerLayer(t);

    for (int i = 0; i < n; ++i) {
        if (col[i] != col[0]) {
            numPerLayer[depth[i]]++;
            vColPerTeamPerLayer[team[i]][depth[i]]++;
        }
        if (team[i] != -1) vPerTeamPerLayer[team[i]][depth[i]]++;
    }
    vector<pair<ll, ll>> resTeam(t, {0, 0});
    for (int i = 0; i < t; ++i) {
        for (auto& [d, k] : vPerTeamPerLayer[i]) {
            resTeam[i].first += min(numPerLayer[d], k);
            resTeam[i].second += min(numPerLayer[d], k) - vColPerTeamPerLayer[i][d];
        }
    }
    for (int i = 0; i < t; ++i) {
        if (resTeam[i].first > res.first) res = resTeam[i];
        else if (resTeam[i].first == res.first && resTeam[i].second > res.second) res = resTeam[i];
    }
    cout << res.first << " " << res.second << endl;
}

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