oj.uz

Submission #120673

# Submission time Handle Problem Language Result Execution time Memory
120673 2019-06-25T07:49:04 Z 송준혁(#2962) Mergers (JOI19_mergers) C++14
0 / 100
 232 ms 41328 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];

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 dfs1(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] = dfs1(v, u, depth+1);
    }
    return E[u];
}

int dfs2(int u, int p){
    int cnt = 0;
    for (int v : adj[u]){
        if (v == p) continue;
        cnt += dfs2(v, u);
    }
    ans -= cnt / 2;
    cnt %= 2;
    if (u != 1 && read(E[u]) - read(S[u]-1) == 0){
        if (!cnt) ans++;
        return 1;
    }
    return cnt;
}

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);
    }

    dfs1(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<=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());
    }
    dfs2(1, 0);
    printf("%d", ans);
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:64: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:66: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:71: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 22 ms 24192 KB Output is correct
2 Correct 22 ms 24320 KB Output is correct
3 Correct 22 ms 24284 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 22 ms 24192 KB Output is correct
6 Correct 22 ms 24192 KB Output is correct
7 Correct 22 ms 24320 KB Output is correct
8 Correct 22 ms 24320 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 22 ms 24184 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24312 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 22 ms 24320 KB Output is correct
3 Correct 22 ms 24284 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 22 ms 24192 KB Output is correct
6 Correct 22 ms 24192 KB Output is correct
7 Correct 22 ms 24320 KB Output is correct
8 Correct 22 ms 24320 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 22 ms 24184 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24312 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 22 ms 24320 KB Output is correct
3 Correct 22 ms 24284 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 22 ms 24192 KB Output is correct
6 Correct 22 ms 24192 KB Output is correct
7 Correct 22 ms 24320 KB Output is correct
8 Correct 22 ms 24320 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 22 ms 24184 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24312 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 38608 KB Output is correct
2 Correct 137 ms 41328 KB Output is correct
3 Incorrect 25 ms 24704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24192 KB Output is correct
2 Correct 22 ms 24320 KB Output is correct
3 Correct 22 ms 24284 KB Output is correct
4 Correct 21 ms 24192 KB Output is correct
5 Correct 22 ms 24192 KB Output is correct
6 Correct 22 ms 24192 KB Output is correct
7 Correct 22 ms 24320 KB Output is correct
8 Correct 22 ms 24320 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 22 ms 24184 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24312 KB Output isn't correct
13 Halted 0 ms 0 KB -