oj.uz

Submission #120720

# Submission time Handle Problem Language Result Execution time Memory
120720 2019-06-25T10:15:30 Z songc Mergers (JOI19_mergers) C++14
0 / 100
 352 ms 56836 KB 
#include <bits/stdc++.h>
using namespace std;

int N, K, ans;
vector<int> adj[505050], chk[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){
    bool tf = read(E[u]) - read(S[u]-1) == 0;
    for (int v : adj[u]){
        if (v == p) chk[u].push_back(ps);
        else chk[u].push_back(dfs2(v, u, tf));
    }
    return tf;
}

bool dfs3(int u, int p){
    bool tf=false;
    for (int i=0; i<(int)adj[u].size(); i++){
        if (adj[u][i] == p) continue;
        bool ret = dfs3(adj[u][i], u);
        if (ret || chk[u][i]) deg[u]++, deg[adj[u][i]]++;
        tf = tf || chk[u][i] || ret;
    }
    return tf;
}

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);
    for (int i=2; i<=N; i++) if (read(E[i]) - read(S[i]-1) == 0){
        dfs3(i, 0);
        break;
    }
    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:70: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:72: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:77: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 Incorrect 32 ms 36096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 36096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 36096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 53788 KB Output is correct
2 Correct 186 ms 56836 KB Output is correct
3 Correct 35 ms 36700 KB Output is correct
4 Correct 36 ms 36620 KB Output is correct
5 Correct 32 ms 36088 KB Output is correct
6 Correct 32 ms 36256 KB Output is correct
7 Correct 36 ms 36600 KB Output is correct
8 Correct 316 ms 56248 KB Output is correct
9 Correct 36 ms 36600 KB Output is correct
10 Incorrect 352 ms 55124 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 36096 KB Output isn't correct
2 Halted 0 ms 0 KB -