oj.uz

Submission #169110

# Submission time Handle Problem Language Result Execution time Memory
169110 2019-12-18T12:10:02 Z Akashi Mergers (JOI19_mergers) C++14
0 / 100
 183 ms 26900 KB 
#include <bits/stdc++.h>
using namespace std;

int n, k;
int h[500005], cul[500005], up[500005], root[500005], nr[500005], nr2[500005];
bool viz[500005], tip[500005];
int d[500005][21];
vector <int> v[500005];

priority_queue <pair <int, int> > L;
void predfs(int nod = 1){
    viz[nod] = 1;

    bool leaf = true;
    for(auto it : v[nod]){
        if(viz[it]) continue ;
        leaf = false;
        h[it] = h[nod] + 1;
        predfs(it);
        d[it][0] = nod;
    }

    viz[nod] = 0;
    if(leaf) L.push({h[nod], nod});
}

inline int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);

    int dif = h[x] - h[y];
    int p = 1, k = 0;
    while(dif){
        if(dif & p) x = d[x][k], dif ^= p;
        p = p << 1; ++k;
    }

    if(x == y) return x;

    for(int t = 20; t >= 0 ; --t)
        if(d[x][t] != d[y][t]) x = d[x][t], y = d[y][t];

    return d[x][0];
}

int main()
{
    scanf("%d%d", &n, &k);
    if(k == 1) {printf("0"); return 0;}
    int x, y;
    for(int i = 1; i < n ; ++i){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    predfs();
    for(int t = 1; t <= 20 ; ++t)
        for(int i = 1; i <= n ; ++i)
            d[i][t] = d[d[i][t - 1]][t - 1];

    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x);
        cul[i] = x;
        if(root[x] == 0) root[x] = i;
        else root[x] = lca(root[x], i);
    }
    for(int i = 1; i <= n ; ++i) up[i] = root[cul[i]];

    int Sol = 0, NR = 0, ad = 0;
    while(!L.empty()){
        int nod = L.top().second;
        L.pop();

        bool leaf = true;
        for(auto it : v[nod]){
            if(it == d[nod][0]) continue ;
            leaf = false;
            nr[nod] += nr[it] + nr2[it];
        }

        int TT = d[nod][0];
        tip[TT] = max(tip[nod], tip[TT]);
        if(up[nod] != nod) up[TT] = lca(up[nod], up[TT]);
        else{
            ++NR;
            if(!tip[nod]){
                tip[TT] = 1, nr[nod] = 1;
                ++ad;
            }
            else{
                if(nr[nod] > 1){
                    Sol = Sol + (nr[nod] - 1) / 2;
                    if(nr[nod] % 2 == 0) nr2[nod] = 1;
                    nr[nod] = 1;
                }

            }
        }
        if(!viz[TT] && TT != 1){
            viz[TT] = 1;
            L.push({h[TT], TT});
        }
    }

//    cerr << ad << endl;
    if(NR == 0) printf("0");
    else{
        int cnt = 0;
        for(auto it : v[1]){
            nr[1] += nr[it] + nr2[it];
            if(nr[it]) ++cnt;
        }

        if(cnt > 1) Sol = Sol + nr[1] / 2 + nr[1] % 2;
        else{
            if(nr[1] > 1){
                Sol = Sol + (nr[1] - 1) / 2;
                if(nr[1] % 2 == 0) nr2[1] = 1;
                nr[1] = 1;
            }
            Sol = Sol + nr[1] + nr2[1];
        }

        printf("%d", Sol);
    }

    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:74:14: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
         bool leaf = true;
              ^~~~
mergers.cpp:47: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:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 26084 KB Output is correct
2 Correct 127 ms 26900 KB Output is correct
3 Correct 15 ms 12536 KB Output is correct
4 Correct 16 ms 12536 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 15 ms 12152 KB Output is correct
7 Correct 15 ms 12536 KB Output is correct
8 Correct 183 ms 26424 KB Output is correct
9 Correct 15 ms 12536 KB Output is correct
10 Incorrect 161 ms 26224 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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