結果

問題 No.2588 Increasing Record
ユーザー 👑 rin204rin204
提出日時 2023-11-24 15:39:49
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 436 ms / 3,000 ms
コード長 6,723 bytes
コンパイル時間 4,076 ms
コンパイル使用メモリ 286,384 KB
実行使用メモリ 36,524 KB
最終ジャッジ日時 2023-12-15 23:31:12
合計ジャッジ時間 16,854 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 2 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 119 ms
6,676 KB
testcase_13 AC 119 ms
6,676 KB
testcase_14 AC 119 ms
6,676 KB
testcase_15 AC 138 ms
6,676 KB
testcase_16 AC 211 ms
11,264 KB
testcase_17 AC 264 ms
18,092 KB
testcase_18 AC 345 ms
25,068 KB
testcase_19 AC 421 ms
30,504 KB
testcase_20 AC 429 ms
31,624 KB
testcase_21 AC 421 ms
31,788 KB
testcase_22 AC 422 ms
31,728 KB
testcase_23 AC 432 ms
31,720 KB
testcase_24 AC 425 ms
31,740 KB
testcase_25 AC 314 ms
18,604 KB
testcase_26 AC 354 ms
24,856 KB
testcase_27 AC 408 ms
31,148 KB
testcase_28 AC 402 ms
30,904 KB
testcase_29 AC 401 ms
31,236 KB
testcase_30 AC 222 ms
18,784 KB
testcase_31 AC 250 ms
26,276 KB
testcase_32 AC 279 ms
32,324 KB
testcase_33 AC 283 ms
33,800 KB
testcase_34 AC 289 ms
33,940 KB
testcase_35 AC 287 ms
33,940 KB
testcase_36 AC 293 ms
33,944 KB
testcase_37 AC 436 ms
31,808 KB
testcase_38 AC 292 ms
18,332 KB
testcase_39 AC 294 ms
30,676 KB
testcase_40 AC 297 ms
31,104 KB
testcase_41 AC 300 ms
32,472 KB
testcase_42 AC 299 ms
33,188 KB
testcase_43 AC 296 ms
36,524 KB
testcase_44 AC 335 ms
21,992 KB
testcase_45 AC 335 ms
26,340 KB
testcase_46 AC 319 ms
29,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include "atcoder/fenwicktree.hpp"
#include "atcoder/modint.hpp"

using mint = atcoder::modint998244353;

struct UnionFind {
    int n;
    vector<int> par;
    vector<int> mx;

    UnionFind(int n) : n(n), par(n, -1), mx(n) {
        iota(mx.begin(), mx.end(), 0);
    }

    int find(int x) {
        if (par[x] < 0) return x;
        return par[x] = find(par[x]);
    }

    void unite(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;
        mx[u]  = max(mx[u], mx[v]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    int get_max(int u) {
        return mx[find(u)];
    }
};

struct HLD {
    int n, path;
    std::vector<std::vector<int>> edges;
    std::vector<int> siz;
    std::vector<int> par;
    std::vector<int> depth;
    std::vector<int> path_ind;
    std::vector<int> path_root;
    std::vector<int> heavy_child;
    std::vector<bool> isheavy;
    std::vector<int> L;
    std::vector<int> R;

    HLD(int n) : n(n) {
        edges.resize(n);
        siz.assign(n, -1);
        par.assign(n, -1);
        depth.assign(n, -1);
        path_ind.assign(n, -1);
        heavy_child.assign(n, -1);
        isheavy.assign(n, false);
        L.assign(n, -1);
        R.assign(n, -1);
    }

    void read_edges(int indexed = 1) {
        int u, v;
        for (int i = 0; i < n - 1; i++) {
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
    }

    void add_edge(int u, int v) {
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void build(int root = 0) {
        depth[root] = 0;
        std::stack<int> st;
        std::vector<int> route;
        st.push(root);
        route.push_back(root);
        while (!st.empty()) {
            int pos = st.top();
            st.pop();
            for (auto npos : edges[pos]) {
                if (depth[npos] == -1) {
                    depth[npos] = depth[pos] + 1;
                    par[npos]   = pos;
                    st.push(npos);
                    route.push_back(npos);
                }
            }
        }
        reverse(route.begin(), route.end());
        for (auto pos : route) {
            siz[pos] = 1;
            int ma   = -1;
            for (auto npos : edges[pos]) {
                if (depth[npos] > depth[pos]) siz[pos] += siz[npos];
                if (siz[npos] > ma) {
                    ma               = siz[npos];
                    heavy_child[pos] = npos;
                }
            }
            if (heavy_child[pos] != -1) isheavy[heavy_child[pos]] = true;
        }
        isheavy[root] = true;

        path = 0;
        st.push(~root);
        st.push(root);
        path_root.push_back(root);
        int cc = 0;
        while (!st.empty()) {
            int pos = st.top();
            st.pop();
            if (pos >= 0) {
                L[pos] = cc++;
                if (!isheavy[pos]) {
                    path++;
                    path_root.push_back(pos);
                }
                path_ind[pos] = path;
                for (auto npos : edges[pos]) {
                    if (npos == par[pos] || npos == heavy_child[pos]) continue;
                    st.push(~npos);
                    st.push(npos);
                }
                if (heavy_child[pos] != -1) {
                    int npos = heavy_child[pos];
                    st.push(~npos);
                    st.push(npos);
                }
            } else {
                pos    = ~pos;
                R[pos] = cc;
            }
        }
    }

    std::vector<std::pair<int, int>> get_path(int u, int v) {
        std::vector<int> ll;
        std::vector<int> rr;
        ll.push_back(u);
        rr.push_back(v);
        while (path_ind[u] != path_ind[v]) {
            if (depth[path_root[path_ind[u]]] >= depth[path_root[path_ind[v]]]) {
                u = path_root[path_ind[u]];
                ll.push_back(u);
                u = par[u];
                ll.push_back(u);
            } else {
                v = path_root[path_ind[v]];
                rr.push_back(v);
                v = par[v];
                rr.push_back(v);
            }
        }
        reverse(rr.begin(), rr.end());
        ll.insert(ll.end(), rr.begin(), rr.end());
        int n = ll.size();
        std::vector<std::pair<int, int>> res(n / 2);
        for (int i = 0; i < n; i += 2) {
            res[i / 2] = {ll[i], ll[i + 1]};
        }
        return res;
    }

    int lca(int u, int v) {
        while (path_ind[u] != path_ind[v]) {
            if (depth[path_root[path_ind[u]]] >= depth[path_root[path_ind[v]]])
                u = par[path_root[path_ind[u]]];
            else
                v = par[path_root[path_ind[v]]];
        }
        return (depth[u] <= depth[v]) ? u : v;
    }

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

    template <typename T>
    std::vector<T> reorder(std::vector<T> &A, bool rev = false) {
        assert(int(A.size()) == n);
        std::vector<T> ret(n);
        for (int i = 0; i < n; i++) {
            ret[L[i]] = A[i];
        }
        if (rev) reverse(ret.begin(), ret.end());
        return ret;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector E(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        E[v - 1].emplace_back(u - 1);
    }

    UnionFind UF(n);
    HLD hld(n);
    for (int v = 0; v < n; v++) {
        for (auto u : E[v]) {
            if (!UF.same(u, v)) {
                hld.add_edge(UF.get_max(u), v);
                UF.unite(u, v);
            }
        }
    }
    hld.build();

    atcoder::fenwick_tree<mint> bit(n);

    for (int v = 0; v < n; v++) {
        vector<pair<int, int>> lr;
        for (auto u : E[v]) {
            auto path = hld.get_path(u, v);
            for (auto [uu, vv] : path) {
                uu = hld.L[uu];
                vv = hld.L[vv];
                if (uu > vv) swap(uu, vv);
                lr.emplace_back(uu, vv + 1);
            }
        }
        sort(lr.begin(), lr.end());
        mint tot = 0;
        int mar  = 0;
        for (auto [l, r] : lr) {
            l = max(l, mar);
            if (l < r) {
                tot += bit.sum(l, r);
            }
            mar = max(mar, r);
        }

        bit.add(hld.L[v], tot + 1);
    }
    mint ans = bit.sum(0, n);
    cout << ans.val() << endl;
}

int main() {
    solve();
}
0