Submission #1241696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241696		CrabCNH	Mergers (JOI19_mergers)	C++20	0 / 100	42 ms	32716 KiB

mergers

#include <bits/stdc++.h>

#define pii pair <int, int>
#define fi first
#define se second

using namespace std;

const int maxN = 5e5 + 5;

int S[maxN], par[maxN], sz[maxN];
vector <int> adj[maxN], all[maxN];
int cnt[maxN];
map <pii, int> mp;
int up[maxN], depth[maxN];

inline void init (int n) {
    for (int i = 1; i <= n; i ++) {
        sz[i] = 1;
        par[i] = i;
    }
}

int getRoot (int u) {
    if (par[u] == u) {
        return u;
    }
    return (par[u] = getRoot (par[u]));
}

inline void join (int u, int v) {
    u = getRoot (u);
    v = getRoot (v);
    if (u == v) {
        return;
    }
    if (sz[u] < sz[v]) {
        swap (u, v);
    }
    par[v] = u;
    sz[u] += sz[v];
    return;
}

inline void merge (int u, int v) {
    while (u != v) {
        //cout << u << ' ' << v << '\n';
        if (depth[u] > depth[v]) {
            swap (u, v);
        }
        join (v, up[v]);
        v = up[v];
    }
}

void dfs (int u, int p) {
    up[u] = p;
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        depth[v] = depth[u] + 1;
        dfs (v, u);
    }
}

int main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    int n, k;
    cin >> n >> k;
    init (n);
    for (int i = 1; i < n; 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];
        all[S[i]].push_back (i);
    }
    dfs (1, 0);
    for (int i = 1; i <= k; i ++) {
        if (all[i].size () <= 1) {
            continue;
        }
        for (int j = 0; j + 1 < (int) all[i].size (); j ++) {
            join (all[i][j], all[i][j + 1]);
        }
    }
    for (int u = 1; u <= n; u ++) {
        for (auto v : adj[u]) {
            if (getRoot (u) != getRoot (v)) {
                cnt[getRoot (u)] ++;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++) {
        int rt = getRoot (i);
        if (rt == i) {
            res += (cnt[i] == 1);
        }
    }
    cout << (res + 1) / 2;
    return 0;
}

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