#916076 (C++17) No.2491 Pochi and A Warp Machine

提出ソース

結果

問題	No.2491 Pochi and A Warp Machine
ユーザー	Cyanmond
提出日時	2023-09-26 23:03:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,137 ms / 3,000 ms
コード長	9,892 bytes
コンパイル時間	3,782 ms
コンパイル使用メモリ	245,440 KB
実行使用メモリ	32,672 KB
最終ジャッジ日時	2023-09-29 14:54:11
合計ジャッジ時間	31,538 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	11 ms 4,376 KB
testcase_10	AC	11 ms 4,380 KB
testcase_11	AC	11 ms 4,376 KB
testcase_12	AC	11 ms 4,380 KB
testcase_13	AC	11 ms 4,376 KB
testcase_14	AC	470 ms 17,832 KB
testcase_15	AC	180 ms 9,764 KB
testcase_16	AC	106 ms 7,332 KB
testcase_17	AC	580 ms 21,064 KB
testcase_18	AC	396 ms 15,816 KB
testcase_19	AC	1,109 ms 31,524 KB
testcase_20	AC	1,137 ms 32,672 KB
testcase_21	AC	948 ms 29,732 KB
testcase_22	AC	975 ms 29,796 KB
testcase_23	AC	1,003 ms 29,716 KB
testcase_24	AC	1,022 ms 29,508 KB
testcase_25	AC	1,012 ms 29,760 KB
testcase_26	AC	994 ms 29,516 KB
testcase_27	AC	954 ms 29,488 KB
testcase_28	AC	990 ms 29,344 KB
testcase_29	AC	981 ms 29,356 KB
testcase_30	AC	985 ms 29,556 KB
testcase_31	AC	1,017 ms 29,616 KB
testcase_32	AC	966 ms 29,896 KB
testcase_33	AC	989 ms 29,704 KB
testcase_34	AC	982 ms 29,536 KB
testcase_35	AC	973 ms 29,660 KB
testcase_36	AC	1,002 ms 29,628 KB
testcase_37	AC	985 ms 29,756 KB
testcase_38	AC	973 ms 29,736 KB
testcase_39	AC	954 ms 29,552 KB
testcase_40	AC	980 ms 29,492 KB
testcase_41	AC	282 ms 29,788 KB
testcase_42	AC	275 ms 29,788 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#include "atcoder/dsu"

using i64 = std::int64_t;

struct TreeManager {
    int n, lg;
    std::vector<std::vector<int>> tree;
    std::vector<int> in, out, par, depth;
    std::vector<std::vector<int>> table;

    TreeManager(const std::vector<std::vector<int>> &tree_) {
        tree = tree_;
        n = (int)tree.size();
        lg = 0;
        while ((1 << lg) < n) ++lg;
        int id = 0;
        in.assign(n, 0);
        out.assign(n, 0);
        par.assign(n, 0);
        depth.assign(n, 0);
        dfs(0, -1, 0, id);
        constructTable();
    }

    void dfs(const int v, const int p, const int d, int &id) {
        in[v] = id++;
        depth[v] = d;
        par[v] = p;
        for (const int t : tree[v]) {
            if (t == p) continue;
            dfs(t, v, d + 1, id);
        }
        out[v] = id++;
    }

    void constructTable() {
        table.resize(lg);
        table[0] = par;
        for (int rank = 1; rank < lg; ++rank) {
            table[rank].assign(n, -1);
            for (int i = 0; i < n; ++i) {
                const int t1 = table[rank - 1][i];
                if (t1 == -1) table[rank][i] = -1;
                else table[rank][i] = table[rank - 1][t1];
            }
        }
    }

    int lca(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int rank = lg - 1; rank >= 0; --rank) {
            const int p = table[rank][v];
            if (p != -1 and depth[p] >= depth[u]) v = p;
        }
        assert(depth[u] == depth[v]);

        if (u == v) return u;
        for (int rank = lg - 1; rank >= 0; --rank) {
            const int a = table[rank][u], b = table[rank][v];
            if (a != b) {
                u = a;
                v = b;
            }
        }
        return par[u];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
};

struct FenwickTree {
    int n;
    std::vector<i64> data;

    FenwickTree(int n_) : n(n_), data(n + 1, 0) {}

    void add(int i, i64 v) {
        ++i;
        while (i <= n) {
            data[i] += v;
            i += i & -i;
        }
    }

    i64 fold(int r) {
        i64 ret = 0;
        while (r != 0) {
            ret += data[r];
            r -= r & -r;
        }
        return ret;
    }

    i64 fold(int l, int r) {
        return fold(r) - fold(l);
    }
};

std::vector<i64> main_(std::vector<int>, std::vector<int>);
std::vector<i64> naive_(std::vector<int>, std::vector<int>);

void randomTest() {
    static constexpr int N = 1000;
    std::mt19937 mt;
    std::uniform_int_distribution<int> dist(0, N - 1);

    int tests = 100;
    while (tests--) {
        std::vector<int> X, Y;
        int cnt = 0;
        atcoder::dsu uft(N);
        while (cnt != N - 1) {
            const int a = dist(mt), b = dist(mt);
            if (uft.same(a, b)) continue;
            uft.merge(a, b);
            X.push_back(a);
            Y.push_back(b);
            ++cnt;
        }

        const auto ans = naive_(X, Y), challanger = main_(X, Y);
        if (ans != challanger) {
            std::cout << "Id : " << tests << std::endl;
            std::cout << N << std::endl;
            for (int i = 0; i < N - 1; ++i) {
                std::cout << X[i] << ' ' << Y[i] << std::endl;
            }
            for (const auto e : challanger) std::cout << e << ' ';
            std::cout << std::endl;
            for (const auto e : ans) std::cout << e << ' ';
            std::cout << std::endl << std::endl;
        }
    }
}

int main() {
    // randomTest();

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<int> X(N - 1), Y(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }
    const auto ans = main_(X, Y);
    for (const auto e : ans) {
        std::cout << e << std::endl;
    }
}

std::vector<i64> main_(std::vector<int> X, std::vector<int> Y) {
    const int N = (int)X.size() + 1;
    std::vector<std::vector<int>> Tree(N);
    for (int i = 0; i < N - 1; ++i) {
        Tree[X[i]].push_back(Y[i]);
        Tree[Y[i]].push_back(X[i]);
    }

    TreeManager sTree(Tree);
    std::vector<int> distList(N);
    for (int i = 1; i < N; ++i){
        distList[i] = sTree.dist(i - 1, i);
    }

    FenwickTree fenTree1(N), fenTree2(N);

    std::vector<bool> isAvailable(N, true);
    std::vector<int> subSize(N);
    std::vector<int> dist1(N, -1), dist2(N, -1);
    std::vector<i64> ans(N);
    auto decomposite = [&](auto &&selfD, const int root) -> void {
        auto dfs1 = [&](auto &&self, const int v, const int p) -> int {
            subSize[v] = 1;
            dist1[v] = dist2[v] = -1;
            for (const int t : Tree[v]) {
                if (t == p) continue;
                if (not isAvailable[t]) continue;
                subSize[v] += self(self, t, v);
            }
            return subSize[v];
        };
        dfs1(dfs1, root, -1);
        const int s = subSize[root];

        auto dfs2 = [&](auto &&self, const int v, const int p) -> int {
            bool isCentroid = true;
            int ret = -1;
            for (const int t : Tree[v]) {
                if (t == p) continue;
                if (not isAvailable[t]) continue;
                const int res = self(self, t, v);
                if (res != -1) return res;
                if (subSize[t] > s / 2) isCentroid = false;
            }
            if (s - subSize[v] > s / 2) isCentroid = false;
            if (isCentroid) ret = v;
            return ret;
        };
        const int centroid = dfs2(dfs2, root, -1);

        std::vector<std::pair<int, int>> qs;
        dist1[centroid] = 0;
        for (const int t : Tree[centroid]) {
            if (not isAvailable[t]) continue;
            std::vector<std::pair<int, int>> qsc;
            auto dfs3 = [&](auto &&self, const int v, const int p, const int d) -> void {
                const int d1 = distList[v];
                if (d1 - 1 >= d) qsc.push_back({d1 - 1 - d, v});
                for (const int t : Tree[v]) {
                    if (t == p) continue;
                    if (not isAvailable[t]) continue;
                    self(self, t, v, d + 1);
                }
            };
            dfs3(dfs3, t, centroid, 1);

            std::sort(qsc.begin(), qsc.end(), [](const auto &a, const auto &b) {
                return a.first < b.first;
            });

            std::queue<int> que;
            que.push(t);
            dist1[t] = 1;
            for (const auto &[a, i] : qsc) {
                fenTree1.add(i, a);
                fenTree2.add(i, 1);
            }

            int r = 0;
            while (not que.empty()) {
                const auto f = que.front();
                que.pop();

                while (r != (int)qsc.size() and qsc[r].first - dist1[f] <= 0) {
                    fenTree1.add(qsc[r].second, -qsc[r].first);
                    fenTree2.add(qsc[r].second, -1);
                    ++r;
                }

                ans[f] -= fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist1[f];
                for (const int to : Tree[f]) {
                    if (not isAvailable[to]) continue;
                    if (dist1[to] != -1) continue;
                    dist1[to] = dist1[f] + 1;
                    que.push(to);
                }
            }
            while (r != (int)qsc.size()) {
                fenTree1.add(qsc[r].second, -qsc[r].first);
                fenTree2.add(qsc[r].second, -1);
                ++r;
            }

            std::copy(qsc.begin(), qsc.end(), std::back_inserter(qs));
        }
        qs.push_back({distList[centroid] - 1, centroid});
        
        std::sort(qs.begin(), qs.end(), [](const auto &a, const auto &b) {
            return a.first < b.first;
        });

        std::queue<int> que;
        que.push(centroid);
        dist2[centroid] = 0;
        for (const auto &[a, i] : qs) {
            fenTree1.add(i, a);
            fenTree2.add(i, 1);
        }

        int r = 0;
        while (not que.empty()) {
            const auto f = que.front();
            que.pop();

            while (r != (int)qs.size() and qs[r].first - dist2[f] <= 0) {
                fenTree1.add(qs[r].second, -qs[r].first);
                fenTree2.add(qs[r].second, -1);
                ++r;
            }

            ans[f] += fenTree1.fold(f + 1, N) - fenTree2.fold(f + 1, N) * dist2[f];
            for (const int to : Tree[f]) {
                if (not isAvailable[to]) continue;
                if (dist2[to] != -1) continue;
                dist2[to] = dist2[f] + 1;
                que.push(to);
            }
        }
        while (r != (int)qs.size()) {
            fenTree1.add(qs[r].second, -qs[r].first);
            fenTree2.add(qs[r].second, -1);
            ++r;
        }

        isAvailable[centroid] = false;
        for (const int t : Tree[centroid]) {
            if (not isAvailable[t]) continue;
            selfD(selfD, t);
        }
    };
    decomposite(decomposite, 0);

    const auto baseAns = std::accumulate(distList.begin(), distList.end(), 0ll);
    for (auto &e : ans) e = baseAns - e;
    return ans;
}

std::vector<i64> naive_(std::vector<int> X, std::vector<int> Y) {
    const int N = (int)X.size() + 1;
    std::vector<std::vector<int>> Tree(N);
    for (int i = 0; i < N - 1; ++i) {
        Tree[X[i]].push_back(Y[i]);
        Tree[Y[i]].push_back(X[i]);
    }

    TreeManager sTree(Tree);
    std::vector<i64> ans(N);
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= i; ++j) {
            ans[i] += sTree.dist(j - 1, j);
        }
        for (int j = i + 1; j < N; ++j) {
            const int a = sTree.dist(j - 1, j), b = sTree.dist(i, j) + 1;
            ans[i] += std::min(a, b);
        }
    }

    return ans;
}

yukicoder

結果

テストケース

ソースコード