Submission #447159

#	Time	Username	Problem	Language	Result	Execution time	Memory
447159		aryan12	Mergers (JOI19_mergers)	C++17	100 / 100	1279 ms	165328 KiB

mergers

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 5;
vector<int> g[N], states[N];
int depth[N];
int DP[20][N];
int par[N];

int Find(int x) {
    if(par[x] == x) {
        return x;
    }
    return par[x] = Find(par[x]);
}

void Unite(int a, int b) {
    a = Find(a), b = Find(b);
    if(depth[a] > depth[b]) {
        swap(a, b);
    }
    par[b] = a;
}

void dfs(int node, int parent) {
    DP[0][node] = parent;
    for(auto i: g[node]) {
        if(i == parent) {
            continue;
        }
        depth[i] = depth[node] + 1;
        dfs(i, node);
    }
}

int LCA(int x, int y) {
    if(depth[x] > depth[y]) {
        swap(x, y);
    }
    int diff = depth[y] - depth[x];
    for(int i = 19; i >= 0; i--) {
        if((1 << i) <= diff) {
            diff -= (1 << i);
            y = DP[i][y];
        }
    }
    if(x == y) {
        return x;
    }
    for(int i = 19; i >= 0; i--) {
        if(DP[i][x] != DP[i][y]) {
            x = DP[i][x];
            y = DP[i][y];
        }
    }
    return DP[0][x];
}

bool cmp(int a, int b) {
    return depth[a] > depth[b];
}

void Solve() {
    for(int i = 0; i < N; i++) {
        par[i] = i;
    }
    int n, k;
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    depth[1] = 1;
    dfs(1, -1);
    for(int i = 1; i < 20; i++) {
        for(int j = 1; j <= n; j++) {
            if(DP[i - 1][j] == -1) {
                DP[i][j] = -1;
            }
            else {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        int cur_state;
        cin >> cur_state;
        states[cur_state].push_back(i);
    }
    for(int i = 1; i <= k; i++) {
        sort(states[i].begin(), states[i].end(), cmp);
        /*cout << "i = " << i << ", size = " << states[i].size() << "\n";
        for(int j = 0; j < states[i].size(); j++) {
            cout << states[i][j] << " ";
        }
        cout << "\n";*/
        int len = states[i].size();
        int node = states[i][0];
        for(int j = 1; j < len; j++) {
            int lca = LCA(node, states[i][j]);
            int cur_node = Find(node);
            while(depth[cur_node] > depth[lca]) {
                Unite(cur_node, DP[0][cur_node]);
                cur_node = Find(cur_node);
            }
            cur_node = Find(states[i][j]);
            while(depth[cur_node] > depth[lca]) {
                Unite(cur_node, DP[0][cur_node]);
                cur_node = Find(cur_node);
            }
            node = lca;
        }
    }
    int degree[n + 1];
    for(int i = 0; i <= n; i++) {
        degree[i] = 0;
    }
    for(int i = 1; i <= n; i++) {
        for(auto j: g[i]) {
            if(Find(j) != Find(i) && j != DP[0][i]) {
                degree[Find(i)]++;
                degree[Find(j)]++;
            }
        }
    }
    int ans = 0;
    /*for(int i = 1; i <= n; i++) {
        cout << degree[i] << " ";
    }
    cout << "\n";
    for(int i = 1; i <= n; i++) {
        cout << Find(i) << " ";
    }
    cout << "\n";*/
    for(int i = 1; i <= n; i++) {
        if(degree[i] == 1) {
            ans++;
        }
    }
    cout << (ans + 1) / 2 << "\n";
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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