oj.uz

답안 #396067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396067 2021-04-29T12:16:46 Z palilo Mergers (JOI19_mergers) C++17
0 / 100
 66 ms 14564 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]);
    }
    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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9296 KB Output is correct
2 Incorrect 66 ms 14564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -