oj.uz

Submission #120706

# Submission time Handle Problem Language Result Execution time Memory
120706 2019-06-25T09:43:01 Z songc Mergers (JOI19_mergers) C++14
0 / 100
 196 ms 41072 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];

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, bool ps){
    int cnt = 0;
    bool sp = (u!=1) && (read(E[u]) - read(S[u]-1) == 0);
    for (int v : adj[u]){
        if (v == p) continue;
        cnt += dfs2(v, u, ps || sp);
    }
    if (sp) {
        if (cnt == 1 && !ps) ans++;
        if (cnt == 0) 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, false);
    printf("%d", (ans+1)/2);
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:65: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:67: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:72: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 27 ms 24192 KB Output is correct
2 Correct 22 ms 24320 KB Output is correct
3 Correct 24 ms 24192 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 32 ms 24184 KB Output is correct
6 Correct 22 ms 24192 KB Output is correct
7 Correct 21 ms 24192 KB Output is correct
8 Correct 22 ms 24188 KB Output is correct
9 Incorrect 21 ms 24312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 38468 KB Output is correct
2 Incorrect 133 ms 41072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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