제출 #1180849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180849		clemmy14	Mergers (JOI19_mergers)	C++20	100 / 100	892 ms	193348 KiB

mergers

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

struct DSU {
    vector<int> e;
    DSU(int N) {e = vector<int>(N, -1);}
    int get(int x) {return e[x] < 0 ? x : e[x]=get(e[x]);}
    int size(int x) {return -e[get(x)];}
    bool unite(int x, int y) {
        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;
    }
};

vector<vector<int>> adj, parent;
vector<int> depth, timeIn;
int curTime=0;

void dfs1(int node, int prev, int dis) {
    depth[node] = dis;
    parent[node][0] = prev;
    timeIn[node]=curTime++;
    for(auto child: adj[node]) if (child != prev) dfs1(child, node, dis+1);
}

int ancestor(int x, int k) {
    int cnt = 0;
    while(k && x) {
        if (k&1) x = parent[x][cnt];
        k = k>>1; cnt++;
    }
    return x;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = ancestor(a, depth[a]-depth[b]);
    if (a==b) return a;
    for(int k=19; k>=0; k--) {
        int aa = parent[a][k];
        int bb = parent[b][k];
        if (aa != bb) {
            a = aa; b = bb;
        }
    }
    return parent[a][0];
}

int n;
vector<int> deg;

void dfs2(int node, int prev, DSU&dsu) {
    for(auto child : adj[node]) if(child != prev) {
        int u=dsu.get(child), v=dsu.get(node);
        if(u != v) {
            deg[u]++;
            deg[v]++;
        }
        dfs2(child, node, dsu);
    }
}

signed main() {
    int k; cin >> n >> k;
    adj = vector<vector<int>>(n+1);
    for(int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    parent = vector<vector<int>>(n+1, vector<int>(20, 0));
    depth = vector<int>(n+1, 0); timeIn = vector<int>(n+1, 0);
    dfs1(1, 0, 0);
    for(int k=1; k<20; k++) {
        for(int i=1; i<=n; i++) {
            if (parent[i][k-1]) parent[i][k] = parent[parent[i][k-1]][k-1];
        }
    }

    vector<int> type(n);
    vector<vector<int>> group(k+1);
    vector<vector<pair<int, int>>> timings(k+1);
    for(int i=0; i<n; i++) {
        cin >> type[i]; 
        group[type[i]].push_back(i+1);
        timings[type[i]].push_back({timeIn[i+1], i+1});
    }

    DSU dsu(n+1);

    for(int i=1; i<=k; i++) if(!group[i].empty()) {
        sort(timings[i].begin(), timings[i].end());
        for(int j=1; j<timings[i].size(); j++) {
            int curLca = lca(timings[i][j].second, timings[i][j-1].second);
            int cur = timings[i][j].second;
            while(cur != curLca) {
                dsu.unite(curLca, cur);
                cur = parent[cur][0];
            }
            cur = timings[i][j-1].second;
            while(cur != curLca) {
                dsu.unite(curLca, cur);
                cur = parent[cur][0];
            }
        }
    }

    deg = vector<int>(n+1, 0);
    dfs2(1, 0, dsu);
    int leaves=0;
    for(auto x : deg) if(x == 1) leaves++;
    cout << (leaves+1)/2;
    return 0;
}

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