#287182 (C++17) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	Suikaba
提出日時	2018-09-26 01:22:53
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	604 ms / 4,500 ms
コード長	9,061 bytes
コンパイル時間	3,447 ms
コンパイル使用メモリ	232,032 KB
実行使用メモリ	60,136 KB
最終ジャッジ日時	2024-04-16 17:28:42
合計ジャッジ時間	12,241 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	7 ms 5,376 KB
testcase_05	AC	8 ms 5,376 KB
testcase_06	AC	8 ms 5,376 KB
testcase_07	AC	7 ms 5,376 KB
testcase_08	AC	473 ms 29,196 KB
testcase_09	AC	480 ms 28,220 KB
testcase_10	AC	504 ms 36,508 KB
testcase_11	AC	496 ms 36,812 KB
testcase_12	AC	408 ms 28,560 KB
testcase_13	AC	400 ms 60,136 KB
testcase_14	AC	479 ms 35,712 KB
testcase_15	AC	597 ms 41,268 KB
testcase_16	AC	604 ms 41,148 KB
testcase_17	AC	515 ms 52,320 KB
testcase_18	AC	529 ms 52,756 KB
testcase_19	AC	524 ms 49,492 KB

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

ソースコード

raw source code

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

using ll = long long;

constexpr int inf = 1e9;

struct edge {
    int from, to;
};

using graph = vector<vector<edge>>;

void add_edge(graph& g, int from, int to) {
    g[from].push_back(edge{from, to});
    g[to].push_back(edge{to, from});
}

class heavy_light_decomposition {
public:
    heavy_light_decomposition(int n_)
        : n(n_), g(n), par(n), head(n), in(n), out(n)
    {}
    heavy_light_decomposition(std::vector<std::vector<int>> const& g_)
        : n(g_.size()), g(g_), par(n), head(n), in(n), out(n)
    {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(int rt = 0) {
        dfs1(rt);
        head[rt] = rt;
        dfs2(rt);
    }

    int get_id(int v) const { return in[v]; }

    void path_query(int u, int v, std::function<void(int, int)> f) { // vertex
        while(true) {
            if(in[u] > in[v]) std::swap(u, v);
            f(std::max(in[head[v]], in[u]), in[v] + 1);
            if(head[u] == head[v]) return;
            v = par[head[v]];
        }
    }
    void edge_path_query(int u, int v, std::function<void(int, int)> f) {
        while(true) {
            if(in[u] > in[v]) std::swap(u, v);
            if(head[u] != head[v]) {
                f(std::max(in[head[v]], in[u]), in[v] + 1);
                v = par[head[v]];
            } else {
                if(u != v) f(in[u] + 1, in[v] + 1);
                break;
            }
        }
    }
    void subtree_query(int v, std::function<void(int, int)> f) {
        f(in[v], out[v]);
    }
    int get_lca(int u, int v) const {
        while(true) {
            if(in[u] > in[v]) std::swap(u, v);
            if(head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

private:
    void dfs1(int rt) {
        std::vector<int> sz(n, 1), iter(n);
        std::vector<std::pair<int, int>> st = {{rt, -1}};
        st.reserve(n);
        while(!st.empty()) {
            const int v = st.back().first;
            if(iter[v] < (int)g[v].size()) {
                if(g[v][iter[v]] != st.back().second) {
                    st.emplace_back(g[v][iter[v]], v);
                }
                ++iter[v];
                continue;
            }
            par[v] = st.back().second;
            if(par[v] != -1) {
                const int pidx = std::find(std::begin(g[v]), std::end(g[v]), par[v]) - std::begin(g[v]);
                std::swap(g[v].back(), g[v][pidx]);
                g[v].pop_back();
            }
            for(auto& u : g[v]) {
                sz[v] += sz[u];
                if(sz[u] > sz[g[v].front()]) std::swap(u, g[v].front());
            }
            st.pop_back();
        }
    }
    void dfs2(int rt) {
        int it = 0;
        std::vector<int> st = {rt}, iter(n);
        st.reserve(n);
        while(!st.empty()) {
            const int v = st.back();
            if(!iter[v]) in[v] = it++; // first visit
            if(iter[v] < (int)g[v].size()) {
                int u = g[v][iter[v]];
                head[u] = iter[v] ? u : head[v];
                st.push_back(u);
                ++iter[v];
                continue;
            }
            out[v] = it;
            st.pop_back();
        }
    }

private:
    const int n;
    std::vector<std::vector<int>> g;
    std::vector<int> par, head, in, out;
};

class lowlink { // multiple edges ok
public:
    lowlink(graph const& g)
        : ord(g.size()), low(g.size())
    {
        const int n = g.size();
        std::vector<bool> visited(n);
        int cnt = 0;
        for(int i = 0; i < n; ++i) {
            if(!visited[i]) {
                dfs(g, i, -1, cnt, visited);
            }
        }
    }

    std::vector<int> get_articulation_points() const { return articulation_points; }
    std::vector<edge> get_bridges() const            { return bridges; }

    bool is_bridge(int u, int v) const {
        if(ord[u] > ord[v]) std::swap(u, v);
        return ord[u] < low[v];
    }

private:
    void dfs(graph const& g, int v, int prev, int& cnt, std::vector<bool>& visited) {
        visited[v] = true;
        low[v] = ord[v] = cnt++;
        bool is_articulation = false;
        int cnt2 = 0, pcnt = 0;

        for(auto& e : g[v]) {
            if((e.to != prev || (e.to == prev && pcnt == 1)) && visited[e.to]) {
                low[v] = min(low[v], ord[e.to]);
            } else if(!visited[e.to]) {
                cnt2++;
                dfs(g, e.to, v, cnt, visited);
                low[v] = min(low[v], low[e.to]);
                if(prev != -1 && ord[v] <= low[e.to]) {
                    is_articulation = true;
                }
                if(is_bridge(v, e.to)) {
                    bridges.push_back(edge{min(v, e.to), max(v, e.to)});
                }
            }
            pcnt += e.to == prev;
        }
        is_articulation |= (prev == -1 && cnt2 > 1);
        if(is_articulation) articulation_points.push_back(v);
    }

private:
    std::vector<int> articulation_points;
    std::vector<edge> bridges;
    std::vector<int> ord, low;
};

class biconnected_component {
public:
    biconnected_component(graph const& g_)
        : g(g_), helper(g_), belongs_(g_.size(), -1)
    {
        for(auto&& b : helper.get_bridges()) {
            add_component(b.from), add_component(b.to);
        }
        add_component(0);
    }

    graph build() { // if not connected, result is forest
        graph res(cmps.size());
        auto bridges = helper.get_bridges();
        for(auto& b : bridges) {
            add_edge(res, belongs(b.from), belongs(b.to));
        }
        return res;
    }

    int belongs(int u) const { return belongs_[u]; }

private:
    void fill_component(int c, int u) {
        cmps[c].emplace_back(u);
        belongs_[u] = c;
        for(auto& e : g[u]) {
            if(belongs_[e.to] >= 0 || helper.is_bridge(u, e.to)) continue;
            fill_component(c, e.to);
        }
    }
    void add_component(int u) {
        if(belongs_[u] >= 0) return;
        cmps.emplace_back();
        fill_component(cmps.size() - 1, u);
    }

private:
    graph g;
    lowlink helper;
    std::vector<int> belongs_;
    std::vector<std::vector<int>> cmps;
};


template<typename Monoid>
class segment_tree {
    using T = typename Monoid::type;

public:
    segment_tree(std::vector<T> const& init)
        : sz(init.size()), n(expand(init.size()))
    {
        dat.assign(n * 2, Monoid::id());
        std::copy(begin(init), end(init), begin(dat) + n);
        for(int i = n - 1; i >= 0; --i) {
            dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]);
        }
    }

    segment_tree(int const n_, T const& init = Monoid::id())
        : segment_tree(std::vector<T>(n_, init))
    {}

    void update(int p, T val) {
        assert(0 <= p && p < sz);
        dat[p += n] = val;
        while(p /= 2) {
            dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]);
        }
    }

    // [l, r)
    T query(int l, int r) const {
        assert(0 <= l && l <= r && r <= sz);
        l += n, r += n;
        T res1 = Monoid::id(), res2 = Monoid::id();
        while(l != r) {
            if(l & 1) res1 = Monoid::op(res1, dat[l++]);
            if(r & 1) res2 = Monoid::op(dat[--r], res2);
            l /= 2, r /= 2;
        }
        return Monoid::op(res1, res2);
    }

private:
    int expand(int n_) const {
        assert(n_ >= 1);
        return n_ == 1 ? n_ : expand((n_ + 1) / 2) * 2;
    }

private:
    const int sz, n;
    std::vector<T> dat;
};

struct RMQ {
    using type = int;
    static type id() {
        return -1;
    }
    static type op(type const& l, type const& r) {
        return std::max(l, r);
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
    graph g(n);
    vector<int> a(m), b(m);
    for(int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        add_edge(g, a[i], b[i]);
    }
    biconnected_component bicc(g);
    g = bicc.build();
    n = g.size();
    heavy_light_decomposition hld(n);
    for(auto& es : g) {
        for(auto& e : es) {
            if(e.from < e.to) hld.add_edge(e.from, e.to);
        }
    }
    hld.build();
    segment_tree<RMQ> seg(n);
    vector<priority_queue<int>> qs(n);
    map<int, int> w_to_v;
    for(int i = 0; i < q; ++i) {
        int qtype; cin >> qtype;
        if(qtype == 1) {
            int u, w; cin >> u >> w;
            u = hld.get_id(bicc.belongs(u - 1));
            w_to_v[w] = u;
            qs[u].push(w);
            seg.update(u, qs[u].top());
        } else {
            int s, t; cin >> s >> t;
            s = bicc.belongs(s - 1), t = bicc.belongs(t - 1);
            int ans = -1;
            hld.path_query(s, t, [&] (int l, int r) { ans = max(ans, seg.query(l, r)); });
            cout << ans << endl;
            if(ans == -1) continue;
            const int v = w_to_v[ans];
            qs[v].pop();
            seg.update(v, qs[v].empty() ? -1 : qs[v].top());
        }
    }
}

yukicoder

結果

テストケース

ソースコード