Submission #396067

#	Time	Username	Problem	Language	Result	Execution time	Memory
396067		palilo	Mergers (JOI19_mergers)	C++17	0 / 100	66 ms	14564 KiB

mergers

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

namespace std {
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template <class Fun>
class y_combinator_result {
    Fun fun_;

public:
    template <class T>
    explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
}; // namespace std

struct disjoint_set {
    vector<int> par;
    disjoint_set(int n) : par(n, -1) {}
    int find(int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;

        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, k;
    cin >> n >> k;

    vector<vector<int>> adj(n);
    for (int i = n - 1, u, v; i--;) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<vector<int>> colour(k);
    for (int i = 0, c; i < n; ++i) {
        cin >> c, --c;
        colour[c].emplace_back(i);
    }

    vector<int> par(n), dep(n);
    par[0] = -1;
    y_combinator([&](auto self, int u) -> void {
        for (const auto& v : adj[u]) {
            if (v == par[u]) continue;
            par[v] = u, dep[v] = dep[u] + 1;
            self(v);
        }
    })(0);

    vector dsu(n, -1);
    auto get_par = [&](int u) {
        while (dsu[u] != -1) {
            if (dsu[dsu[u]] != -1) dsu[u] = dsu[dsu[u]];
            u = dsu[u];
        }
        return u;
    };

    for (const auto& nodes : colour) {
        int u = get_par(nodes[0]), p;
        for (auto v : nodes) {
            for (v = get_par(v); u != v; u = p) {
                if (dep[u] < dep[v]) swap(u, v);
                p = get_par(par[u]);
                dsu[u] = p;
            }
        }
    }

    vector<bool> is_leaf(n);
    for (int i = 1; i < n; ++i)
        if (i == get_par(i))
            is_leaf[i] = true;

    y_combinator([&](auto self, int u) -> void {
        for (const auto& v : adj[u]) {
            if (v == par[u]) continue;
            if (get_par(u) != get_par(v))
                is_leaf[get_par(u)] = false;
            self(v);
        }
    })(0);
    cout << ((count(is_leaf.begin(), is_leaf.end(), true) + 1) >> 1);
}

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