Submission #863879

#	Time	Username	Problem	Language	Result	Execution time	Memory
863879		lolismek	Mergers (JOI19_mergers)	C++14	100 / 100	1063 ms	141136 KiB

mergers

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int NMAX = 5e5;
const int LGMAX = 19;

vector <int> adj[NMAX + 1];
int s[NMAX + 1];

int lvl[NMAX + 1];
int dp[NMAX + 1][LGMAX + 1];

void dfs1(int node, int parent){
    lvl[node] = lvl[parent] + 1;
    dp[node][0] = parent;

    for(int child : adj[node]){
        if(child != parent){
            dfs1(child, node);
        }
    }
}

int LCA(int a, int b){
    if(lvl[a] < lvl[b]){
        swap(a, b);
    }

    int diff = lvl[a] - lvl[b];
    for(int i = LGMAX; i >= 0; i--){
        if(diff & (1 << i)){
            a = dp[a][i];
        }
    }

    if(a == b){
        return a;
    }

    for(int i = LGMAX; i >= 0; i--){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i];
            b = dp[b][i];
        }
    }

    return dp[a][0];
}

int glca[NMAX + 1];
int bad[NMAX + 1];

int dfs2(int node, int parent){
    int mini = lvl[glca[s[node]]];

    for(int child : adj[node]){
        if(child != parent){
            mini = min(mini, dfs2(child, node));
        }
    }

    if(mini >= lvl[node]){
        bad[node] = parent;
    }

    return mini;
}

int Id = 0;
int id[NMAX + 1];

void dfs3(int node, int parent){
    if(bad[node] == parent){
        id[node] = ++Id;
    }else{
        id[node] = id[parent];
    }

    for(int child : adj[node]){
        if(child != parent){
            dfs3(child, node);
        }
    }
}

vector <int> T[NMAX + 1];

void dfs4(int node, int parent){
    for(int child : adj[node]){
        if(child != parent){
            if(id[child] != id[node]){
                T[id[node]].push_back(id[child]);
                T[id[child]].push_back(id[node]);
            }
            dfs4(child, node);
        }
    }
}

int main(){

    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        cin >> s[i];
    }

    dfs1(1, 0);

    for(int j = 1; (1 << j) <= n; j++){
        for(int i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    for(int i = 1; i <= n; i++){
        if(glca[s[i]] == 0){
            glca[s[i]] = i;
        }else{
            glca[s[i]] = LCA(glca[s[i]], i);
        }
    }

    dfs2(1, 0);
    dfs3(1, 0);
    dfs4(1, 0);

    int leafs = 0;
    for(int i = 1; i <= Id; i++){
        sort(T[i].begin(), T[i].end());
        T[i].erase(unique(T[i].begin(), T[i].end()), T[i].end());

        if((int)T[i].size() == 1){
            leafs++;
        }
    }

    cout << (leafs / 2) + (leafs % 2) << '\n';

    return 0;
}

/*
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4
*/

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