Submission #1206644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206644		ocean	Team Coding (EGOI24_teamcoding)	C++17	39 / 100	61 ms	36084 KiB

Main

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

struct FastIO {                          // minimal fast input
    FastIO()   { ios::sync_with_stdio(false); cin.tie(nullptr); }
} fastio;

int main() {
    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<int> lang(N);
    for (int &x : lang) cin >> x;

    vector<vector<int>> g(N);
    for (int i = 1; i < N; ++i) {
        int boss; cin >> boss;
        g[boss].push_back(i);
    }

    /* ---------- Euler tour & basic tables ---------- */
    vector<int> tin(N), tout(N), depth(N), euler;
    vector<vector<int>> depthNodes;              // tin indices per depth
    vector<vector<int>> langTin(K);              // tin indices per language
    vector<vector<int>> langDepthRaw(K);         // raw depth list per language
    vector<int> shallowNode(K, -1), shallowDep(K, INT_MAX);

    int timer = 0;
    function<void(int,int)> dfs = [&](int u, int dep) {
        depth[u] = dep;
        if ((int)depthNodes.size() <= dep) depthNodes.emplace_back();
        tin[u] = timer++;
        depthNodes[dep].push_back(tin[u]);

        int c = lang[u];
        langTin[c].push_back(tin[u]);
        langDepthRaw[c].push_back(dep);
        if (dep < shallowDep[c]) { shallowDep[c] = dep; shallowNode[c] = u; }

        for (int v : g[u]) dfs(v, dep + 1);
        tout[u] = timer - 1;
    };
    dfs(0, 0);

    /* ---------- compress (depth , count) per language ---------- */
    vector<vector<pair<int,int>>> langDepthCnt(K);
    for (int c = 0; c < K; ++c) {
        auto &vec = langDepthRaw[c];
        if (vec.empty()) continue;
        sort(vec.begin(), vec.end());
        for (std::size_t i = 0, j; i < vec.size(); i = j) {
            j = i;
            while (j < vec.size() && vec[j] == vec[i]) ++j;
            langDepthCnt[c].push_back({vec[i], int(j - i)});
        }
    }

    /* ---------- helpers ---------- */
    auto countInSub = [&](const vector<int>& arr, int L, int R) -> int {
        auto lo = lower_bound(arr.begin(), arr.end(), L);
        auto hi = upper_bound(arr.begin(), arr.end(), R);
        return int(hi - lo);
    };

    /* ---------- scan all languages' shallowest leaders ---------- */
    long long bestTeam = -1, bestSwaps = 0;

    for (int c = 0; c < K; ++c) {
        int lead = shallowNode[c];
        if (lead == -1) continue;                       // language unused

        int L = tin[lead], R = tout[lead];

        long long team = 0;
        for (auto [d, cntLangDepth] : langDepthCnt[c]) {
            const auto &vec = depthNodes[d];
            int S = countInSub(vec, L, R);
            team += min<long long>(S, cntLangDepth);
        }

        int initial = countInSub(langTin[c], L, R);
        long long swaps = team - initial;

        if (team > bestTeam || (team == bestTeam && swaps < bestSwaps)) {
            bestTeam  = team;
            bestSwaps = swaps;
        }
    }

    cout << bestTeam << ' ' << bestSwaps << '\n';
    return 0;
}

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