Submission #1183270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183270		gubshig	Mergers (JOI19_mergers)	C++20	0 / 100	63 ms	44224 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 500'000 + 50;

int N, K;
int S[MAX_N], Cnt[MAX_N], Dp[MAX_N];
bool IsStar[MAX_N];
map<int, int> Mp[MAX_N];
vector<int> Adj[MAX_N];

void Dfs(int v=1, int p=0) {
    if (Cnt[S[v]] > 1) Mp[v][S[v]]++;
    for (auto &nxt: Adj[v]) {
        if (nxt == p) continue;

        Dfs(nxt, v);

        Dp[v] += Dp[nxt];

        if (Mp[nxt].size() > Mp[v].size()) swap(Mp[nxt], Mp[v]);
        for (auto &[s, c]: Mp[nxt]) {
            Mp[v][s] += c;
            if (Mp[v][s] == Cnt[s]) Mp[v].erase(s);
        }
    }

    if (v != 1 && Mp[v].empty()) {
        IsStar[v] = true;
        if (Dp[v] == 0) Dp[v] = 1;
    }
}

vector<int> I;
void GetI(int v=1, int p=0) {
    if (IsStar[v]) {
        I.push_back(Dp[v]);
        return;
    }

    for (auto &nxt: Adj[v]) {
        if (nxt == p) continue;

        GetI(nxt, v);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> N >> K;
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }

    for (int i = 1; i <= N; i++) {
        cin >> S[i];
        Cnt[S[i]]++;
    }

    Dfs();
    GetI();
    vector<vector<int>> vp(2);
    int s = 0;
    for (auto &i: I) {
        vp[i % 2].push_back(i);
        s += i;
    }

    int ans = s / 2;
    if ((vp[1].size() % 2) == 1) ans++;

    cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30