제출 #1179194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179194		igofan	Mergers (JOI19_mergers)	C++20	0 / 100	36 ms	12432 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }
    // get representive component (uses path compression)
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
    bool same_set(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {  // union by size
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<int>> adj(n+1);
    for(int i=0; i<n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    DSU dsu(n+1);
    vector<vector<int>> st(k+1);
    for(int i=1; i<=n; i++) {
        int state; cin >> state;
        st[state].push_back(i);
    }
    for(int i=1; i<=k; i++) {
        for(int j=1; j<st[i].size(); j++) {
            dsu.unite(st[i][0], st[i][j]);
        }
    }
    vector<int> degree(n+1, 0);
    for(int i=1; i<=n; i++) {
        int u = dsu.get(i);
        for(auto j : adj[i]) {
            if (i > j) continue;
            int v = dsu.get(j);
            if (u == v) continue;
            degree[u]++;
            degree[v]++;
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++) {
        if (degree[i] == 1) {
            ans++;
        }
    }
    ans = (ans + 1)/2;
    cout << ans << '\n';
    return 0;
}

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