Submission #169091

#	Time	Username	Problem	Language	Result	Execution time	Memory
169091		Akashi	Mergers (JOI19_mergers)	C++14	0 / 100	123 ms	29040 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

int n, k;
int h[500005], cul[500005], f[500005], up[500005], root[500005], nr[500005];
bool viz[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);

    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);
        ++f[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];
        }

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

        int TT = d[nod][0];
        if(up[nod] != nod) up[TT] = lca(up[nod], up[TT]);
        else ++NR;

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

    if(NR == 1) printf("0");
    else printf("%d", Sol + 1);

    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30