Submission #604404

#	Time	Username	Problem	Language	Result	Execution time	Memory
604404		tengiz05	Mergers (JOI19_mergers)	C++17	0 / 100	96 ms	26536 KiB

mergers

#include <bits/stdc++.h>

using i64 = long long;

using namespace std;

struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) { return leader(x) == leader(y); }
    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return siz[leader(x)]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    vector<int> s(n);
    vector<int> L(k);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        s[i]--;
        L[s[i]] = i;
    }
    
    vector<int> in(n), out(n);
    vector up(n, vector<int>(20));
    int timeStamp = 0;
    
    function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = timeStamp++;
        up[u][0] = p;
        for (int i = 1; i < 20; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : e[u]) {
            if (v != p) {
                dfs(v, u);
            }
        }
        out[u] = timeStamp;
    };
    
    dfs(0, 0);
    
    cerr << "How ";
    
    auto is = [&](int u, int v) {
        return in[u] <= in[v] && out[u] >= out[v];
    };
    auto lca = [&](int u, int v) {
        if (is(u, v)) return u;
        if (is(v, u)) return v;
        for (int i = 19; i >= 0; i--) {
            if (!is(up[u][i], v)) {
                u = up[u][i];
            }
        }
        return up[u][0];
    };
    
    for (int i = 0; i < n; i++) {
        L[s[i]] = lca(L[s[i]], i);
    }
    
    vector<int> cum(n);
    for (int i = 0; i < n; i++) {
        cum[i]++;
        cum[L[s[i]]]--;
    }
    
    cerr << "are ";
    
    DSU dsu(n);
    
    function<int(int, int)> dfs2 = [&](int u, int p) {
        int sum = cum[u];
        for (int v : e[u]) {
            if (v != p) {
                sum += dfs2(v, u);
            }
        }
        if (sum) {
            dsu.merge(u, p);
        }
        return sum;
    };
    
    dfs2(0, -1);
    
    cerr << "you ";
    
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        for (int j : e[i]) {
            int u = dsu.leader(i);
            int v = dsu.leader(j);
            if (i != j) {
                adj[u].push_back(v);
            }
        }
    }
    
    cerr << "doing?\n";
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += adj[i].size() == 1;
    }
    
    cout << (cnt + 1) / 2 << "\n";
    
    return 0;
}

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