Submission #169117

#	Time	Username	Problem	Language	Result	Execution time	Memory
169117		Akashi	Mergers (JOI19_mergers)	C++14	100 / 100	1337 ms	115804 KiB

mergers

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

int n, k, Sol;
int h[500005], cul[500005], up[500005], root[500005], nr[500005], nr2[500005], cnt[500005];
bool viz[500005], tip[500005], mark[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];
}

void dfs(int nod, int rad, int type){
    viz[nod] = 1;

    for(auto it : v[nod]){
        if(viz[it]) continue ;
        if(mark[it]){
            dfs(it, it, 1);
            nr[rad] += nr[it] + nr2[it];
            ++cnt[rad];
        }
        else dfs(it, rad, 0);
    }

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

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &k);
    if(n == 1 || 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 NR = 0;
    while(!L.empty()){
        int nod = L.top().second;
        L.pop();

        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;
            mark[nod] = 1;
            if(!tip[nod]) tip[TT] = 1, nr[nod] = 1;
        }

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

    if(NR == 0) printf("0");
    else{
        memset(viz, 0, sizeof(viz));
        mark[1] = 1;
        dfs(1, 1, 1);

        printf("%d", Sol);
    }

    return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:82: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:86: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:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30