oj.uz

Submission #393432

# Submission time Handle Problem Language Result Execution time Memory
393432 2021-04-23T12:19:15 Z palilo None (KOI18_family) C++17
0 / 100
 1 ms 204 KB 
#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]);
    }
    int get_size(int u) {
        u = find(u);
        return -par[u];
    }
    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

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

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

    int root1 = -1, root2 = -1;
    vector<vector<int>> tree1(n1), tree2(n2);
    for (int i = 0, p; i < n1; ++i) {
        cin >> p, --p;
        if (p == -1) root1 = i;
        else
            tree1[p].emplace_back(i);
    }
    for (int i = 0, p; i < n2; ++i) {
        cin >> p, --p;
        if (p == -1) root2 = i;
        else
            tree2[p].emplace_back(i);
    }

    assert(~root1 && ~root2);

    auto dfs = [&](vector<vector<int>>& tree, int root) {
        vector<int> dp(tree.size());
        fill(dp.begin(), dp.begin() + k, 1);

        vector<int> leaf(tree.size());
        iota(leaf.begin(), leaf.begin() + k, 0);

        y_combinator([&](auto self, int u) -> void {
            for (const auto& v : tree[u]) {
                self(v);
                dp[u] += dp[v];
                leaf[u] = leaf[v];
            }
        })(root);
        return make_pair(dp, leaf);
    };

    const auto [dp1, leaf1] = dfs(tree1, root1);
    const auto [dp2, leaf2] = dfs(tree2, root2);

    assert(dp1[root1] == k);
    assert(dp2[root2] == k);

    vector<int> vtx((n1 - k) + (n2 - k));
    iota(vtx.begin(), vtx.begin() + n1 - k, k);
    iota(vtx.begin() + n1 - k, vtx.end(), n1 + k);
    sort(vtx.begin(), vtx.end(), [&](auto& a, auto& b) {
        return (a < n1 ? dp1[a] : dp2[a - n1]) < (b < n1 ? dp1[b] : dp2[b - n1]);
    });

    disjoint_set dsu(k);

    for (auto u : vtx) {
        const auto& tree = u < n1 ? tree1 : tree2;
        const auto& dp = u < n1 ? dp1 : dp2;
        const auto& leaf = u < n1 ? leaf1 : leaf2;
        if (u >= n1) u -= n1;

        assert(!tree[u].empty());

        const auto& first_leaf = leaf[tree[u].front()];
        for (const auto& v : tree[u])
            dsu.merge(first_leaf, leaf[v]);

        if (dp[u] != dsu.get_size(first_leaf))
            return cout << "NO", 0;
    }
    cout << "YES";
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -