oj.uz

Submission #120618

# Submission time Handle Problem Language Result Execution time Memory
120618 2019-06-25T05:44:21 Z 송준혁(#2962) Mergers (JOI19_mergers) C++14
0 / 100
 303 ms 41200 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);
    }
    if (u == 1){
        ans -= cnt / 2;
        return 0;
    }
    if (read(E[u]) - read(S[u]-1) == 0){
        ans -= cnt / 2;
        if (~cnt & 1) 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++){
        if (rst[i].empty()) continue;
        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:67: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:69: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:74: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 24184 KB Output is correct
2 Correct 23 ms 24192 KB Output is correct
3 Correct 23 ms 24192 KB Output is correct
4 Correct 22 ms 24320 KB Output is correct
5 Correct 22 ms 24232 KB Output is correct
6 Correct 23 ms 24320 KB Output is correct
7 Correct 25 ms 24312 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24320 KB Output is correct
10 Correct 23 ms 24192 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24192 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 24184 KB Output is correct
2 Correct 23 ms 24192 KB Output is correct
3 Correct 23 ms 24192 KB Output is correct
4 Correct 22 ms 24320 KB Output is correct
5 Correct 22 ms 24232 KB Output is correct
6 Correct 23 ms 24320 KB Output is correct
7 Correct 25 ms 24312 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24320 KB Output is correct
10 Correct 23 ms 24192 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24192 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 24184 KB Output is correct
2 Correct 23 ms 24192 KB Output is correct
3 Correct 23 ms 24192 KB Output is correct
4 Correct 22 ms 24320 KB Output is correct
5 Correct 22 ms 24232 KB Output is correct
6 Correct 23 ms 24320 KB Output is correct
7 Correct 25 ms 24312 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24320 KB Output is correct
10 Correct 23 ms 24192 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 38604 KB Output is correct
2 Correct 132 ms 41200 KB Output is correct
3 Incorrect 26 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 24184 KB Output is correct
2 Correct 23 ms 24192 KB Output is correct
3 Correct 23 ms 24192 KB Output is correct
4 Correct 22 ms 24320 KB Output is correct
5 Correct 22 ms 24232 KB Output is correct
6 Correct 23 ms 24320 KB Output is correct
7 Correct 25 ms 24312 KB Output is correct
8 Correct 24 ms 24184 KB Output is correct
9 Correct 25 ms 24320 KB Output is correct
10 Correct 23 ms 24192 KB Output is correct
11 Correct 22 ms 24192 KB Output is correct
12 Incorrect 23 ms 24192 KB Output isn't correct
13 Halted 0 ms 0 KB -