結果

問題 No.828 全方位神童数
ユーザー PachicobuePachicobue
提出日時 2019-04-11 02:32:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,121 bytes
コンパイル時間 819 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-07-19 07:12:44
合計ジャッジ時間 11,867 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <cassert>
#include <numeric>
class UnionFind
{
public:
    UnionFind(const std::size_t v) : V(v), parent(v), size(v, 1) { std::iota(parent.begin(), parent.end(), 0); }
    std::size_t find(const std::size_t a) { return assert(a < V), parent[a] == a ? a : parent[a] = find(parent[a]); }
    bool same(const std::size_t a, const std::size_t b)
    {
        assert(a < V), assert(b < V);
        return find(a) == find(b);
    }
    void unite(std::size_t a, std::size_t b)
    {
        assert(a < V), assert(b < V);
        a = find(a), b = find(b);
        if (a == b) { return; }
        if (size[a] < size[b]) { std::swap(a, b); }
        size[a] += size[b], parent[b] = a;
    }
    std::size_t getSize(const std::size_t a) { return assert(a < V), size[find(a)]; }
    void debugPrint() const
    {
        std::cerr << "[";
        for (std::size_t i = 0; i < parent.size(); i++) { std::cerr << parent[i] << (i + 1 == parent.size() ? "" : ","); }
        std::cerr << "]\n";
    }

private:
    const std::size_t V;
    std::vector<std::size_t> parent, size;
};
int main()
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::size_t N;
    std::cin >> N;
    std::vector<std::vector<std::size_t>> G(N);
    for (std::size_t i = 0; i < N - 1; i++) {
        std::size_t u, v;
        std::cin >> u >> v, u--, v--;
        G[u].push_back(v), G[v].push_back(u);
    }
    UnionFind uf(N);
    std::vector<std::size_t> max(N);
    std::vector<std::vector<std::size_t>> G2(N);
    for (std::size_t i = 0; i < N; i++) {
        for (const std::size_t to : G[i]) {
            if (to > i) { continue; }
            const std::size_t c = max[uf.find(to)];
            G2[i].push_back(c), uf.unite(i, c);
        }
        max[uf.find(i)] = i;
    }
    std::vector<std::size_t> ans(N, 1);
    auto dfs = [&](auto&& self, const std::size_t s) -> void {
        for (const std::size_t to : G2[s]) { ans[to] = ans[s] + 1, self(self, to); }
    };
    dfs(dfs, N - 1);
    for (std::size_t i = 0; i < N; i++) { std::cout << ans[i] << "\n"; }
    return 0;
}
0