oj.uz

Submission #169097

# Submission time Handle Problem Language Result Execution time Memory
169097 2019-12-18T11:42:12 Z Akashi Mergers (JOI19_mergers) C++14
0 / 100
 129 ms 26828 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()
{
//    freopen("1.in", "r", stdin);
    scanf("%d%d", &n, &k);

    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;
    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] = tip[nod];
        if(up[nod] != nod) up[TT] = lca(up[nod], up[TT]);
        else{
            ++NR;
            if(!tip[nod]) tip[TT] = 1, nr[nod] = 1;
            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});
        }
    }

    if(NR == 0) printf("0");
    else{
        int n1 = 0, n2 = 0;
        int cnt = 0;
        for(auto it : v[1]){
            n1 += nr[it];
            n2 += nr2[it];
            if(nr[it]) ++cnt;
        }

        if(cnt > 1) Sol = Sol + (n1 + n2) / 2 + (n1 + n2) % 2;
        else Sol = Sol + n1 + n2;

        printf("%d", Sol);
    }

    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:75:14: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
         bool leaf = true;
              ^~~~
mergers.cpp:48: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:52: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:63: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 12 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 26132 KB Output is correct
2 Correct 129 ms 26828 KB Output is correct
3 Incorrect 16 ms 12636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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