Submission #120834

#	Time	Username	Problem	Language	Result	Execution time	Memory
120834		songc	Mergers (JOI19_mergers)	C++14	0 / 100	161 ms	43544 KiB

mergers

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

int N, K, ans;
vector<int> adj[505050];
vector<int> rst[505050];
int S[505050], E[505050], num=1;
int st[505050], T[505050];
int P[22][505050], dep[505050];
int deg[505050], pa[505050];

void update(int t, int v){
    while (t <= N){
        T[t] += v;
        t += t & -t;
    }
}

int read(int t){
    int ret=0;
    while (t){
        ret += T[t];
        t ^= t & -t;
    }
    return ret;
}

int Find(int u){
    if (u == pa[u]) return u;
    return pa[u] = Find(pa[u]);
}

int dfs(int u, int p, int depth){
    P[0][u] = p;
    S[u] = num;
    E[u] = num++;
    dep[u] = depth;
    for (int v : adj[u]){
        if (v == p) continue;
        E[u] = dfs(v, u, depth+1);
    }
    return E[u];
}

void Union(int u, int p){
    if (read(E[u]) - read(S[u]-1) != 0) pa[Find(u)] = Find(p);
    for (int v : adj[u]){
        if (v == p) continue;
        Union(v, u);
    }
}

int LCA(int u, int v){
    if (dep[u] < dep[v]) swap(u, v);
    for (int i=20; i>=0; i--) if (dep[P[i][u]] >= dep[v]) u = P[i][u];
    if (u == v) return u;
    for (int i=20; i>=0; i--) if (P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}

int main(){
    int u, v;
    scanf("%d %d", &N, &K);
    for (int i=1; i<N; i++){
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1; i<=N; i++){
        scanf("%d", &st[i]);
        rst[st[i]].push_back(i);
    }

    dfs(1, 0, 1);
    for (int i=1; i<=N; i++) update(i, 1);
    for (int i=1; i<=20; i++) for (int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
    for (int i=1; i<=N; i++) pa[i] = i;
    for (int i=1; i<=K; i++){
        int lca = rst[i][0];
        for (int j=1; j<(int)rst[i].size(); j++) lca = LCA(lca, rst[i][j]);
        update(S[lca], -rst[i].size());
    }
    Union(1, 0);
    for (int i=1; i<=N; i++) for (int j : adj[i]) if (Find(i) != Find(j)) deg[j]++;
    for (int i=1; i<=N; i++) if (deg[i] == 1) ans++;
    printf("%d", (ans+1)/2);
    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &st[i]);
         ~~~~~^~~~~~~~~~~~~~

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