oj.uz

Submission #120834

# Submission time Handle Problem Language Result Execution time Memory
120834 2019-06-25T15:30:43 Z songc Mergers (JOI19_mergers) C++14
0 / 100
 161 ms 43544 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Incorrect 26 ms 24320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Incorrect 26 ms 24320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Incorrect 26 ms 24320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 40408 KB Output is correct
2 Correct 136 ms 43544 KB Output is correct
3 Incorrect 26 ms 24824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24320 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Incorrect 26 ms 24320 KB Output isn't correct
4 Halted 0 ms 0 KB -