#387776 (C++14) No.529 帰省ラッシュ

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	toma
提出日時	2019-10-08 00:03:39
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	10,130 bytes
コンパイル時間	3,164 ms
コンパイル使用メモリ	225,720 KB
実行使用メモリ	228,932 KB
最終ジャッジ日時	2024-10-15 04:25:56
合計ジャッジ時間	27,785 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	16 ms 5,248 KB
testcase_05	AC	16 ms 5,248 KB
testcase_06	AC	16 ms 5,248 KB
testcase_07	AC	16 ms 5,248 KB
testcase_08	AC	1,330 ms 45,540 KB
testcase_09	AC	1,497 ms 51,540 KB
testcase_10	AC	2,238 ms 76,520 KB
testcase_11	AC	2,238 ms 76,948 KB
testcase_12	AC	972 ms 42,392 KB
testcase_13	TLE	-
testcase_14	AC	997 ms 48,828 KB
testcase_15	AC	2,467 ms 78,952 KB
testcase_16	AC	2,511 ms 79,208 KB
testcase_17	AC	1,214 ms 59,308 KB
testcase_18	AC	1,183 ms 59,272 KB
testcase_19	AC	1,207 ms 57,172 KB

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

ソースコード

raw source code

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;

using Graph = vector<vector<int>>;
struct LowLink {
    vector<int> articulation;
    vector<pair<int, int>> bridge;
    LowLink(const Graph& g) :g(g) {}
    virtual void build() {
        const int N = g.size();
        used.assign(N, 0);
        ord.assign(N, 0);
        low.assign(N, 0);
        int k = 0;
        rep(i, N)if (!used[i])k = dfs(i, k, -1);
    }

protected:
    const Graph& g;
    vector<int> used, ord, low;
    int dfs(int idx, int k, int par) {
        used[idx] = true;
        ord[idx] = k++;
        low[idx] = ord[idx];
        bool is_articulation = false;
        int cnt = 0;

        for (const auto& to : g[idx]) {
            if (!used[to]) {
                ++cnt;
                k = dfs(to, k, idx);
                low[idx] = min(low[idx], low[to]);
                is_articulation |= ~par && low[to] >= ord[idx];
                if (ord[idx] < low[to])bridge.emplace_back(minmax(idx, to));
            }
            else if (to != par) {
                low[idx] = min(low[idx], ord[to]);
            }
        }
        is_articulation |= par == -1 && cnt > 1;
        if (is_articulation) {
            articulation.push_back(idx);
        }
        return k;
    }
};
class UnionFind {
public:
    vector<int>rank, parent;
    //初期化
    UnionFind(int size) {
        rank.resize(size, 0);
        parent.resize(size, 0);
        rep(i, size)parent[i] = i;
    }
    //木の根を求める
    int find(int x) {
        if (parent[x] == x)return x;
        else return parent[x] = find(parent[x]);
    }
    //xとyの属する集合を併合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])
            parent[x] = y;
        else {
            parent[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
    }
    //xとyが同じ集合に属するか否か
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
};
struct TwoEdgeConnectedComponents {
    /* 二重辺連結成分分解
     * 依存
     * - LowLink
     * - UnionFind
     */
    vector<int> trans; // index -> new index (clustered)
    vector<vector<int>> ngraph; // new index -> new edges (clustered)

    TwoEdgeConnectedComponents(Graph& old_graph) {
        const int N = old_graph.size();
        auto edges = rebuild_edges(old_graph);
        auto bridges = get_bridge(old_graph);

        auto uf = make_uf(N, edges, bridges);
        trans = make_trans(N, uf);
        ngraph = create_ngraph(bridges, trans);
    }
private:
    set<pair<int, int>> rebuild_edges(const Graph& graph) {
        set<pair<int, int>> res;
        rep(i, graph.size())
            for (int j : graph[i])
                if (i < j)
                    res.emplace(i, j);
        return res;
    }
    set<pair<int, int>> get_bridge(const Graph& graph) {
        LowLink lowlink(graph);
        lowlink.build();

        set<pair<int, int>> bridges;
        for (auto& bridge : lowlink.bridge) {
            if (bridge.first > bridge.second) {
                swap(bridge.first, bridge.second);
            }
            bridges.insert(bridge);
        }
        return bridges;
    }
    UnionFind make_uf(
        const int N,
        const set<pair<int, int>>& edges,
        const set<pair<int, int>>& bridges
    ) {
        UnionFind uf(N);
        for (const auto& edge : edges) {
            if (bridges.find(edge) != bridges.end())continue;
            uf.unite(edge.first, edge.second);
        }
        return uf;
    }
    vector<int> make_trans(
        const int N,
        UnionFind& uf
    ) {
        int cnt = 0;
        set<int> st;
        map<int, int> mp;
        rep(i, N)st.insert(uf.find(i));
        for (int num : st)mp[num] = cnt++;

        vector<int> trans;
        rep(i, N)trans.push_back(mp[uf.find(i)]);
        return trans;
    }
    vector<vector<int>> create_ngraph(
        const set<pair<int, int>>& bridges,
        const vector<int>& trans
    ) {
        const int M = *max_element(trans.begin(), trans.end()) + 1;
        vector<vector<int>> ngraph(M);
        for (const auto& bridge : bridges) {
            int l = trans[bridge.first];
            int r = trans[bridge.second];
            ngraph[l].push_back(r);
            ngraph[r].push_back(l);
        }
        return ngraph;
    }
};


class SegmentTree {
private:
    int n; // 横幅
    vector<set<int, function<bool(const int&, const int&)>>> data;
    map<int, int> val2idx;

public:
    // init忘れに注意
    SegmentTree() {}
    void init(int n_) {
        auto comp = [](const int& l, const int& r) {return l > r; };

        n = 1;
        while (n < n_)n <<= 1;
        data.resize(n << 1, set<int, function<bool(const int&, const int&)>>(comp));
    }
    void add_val(int idx, const int val) {
        val2idx[val] = idx;
        idx += n;
        do {
            data[idx].insert(val);
        } while (idx >>= 1);
    }
    void erase_val(const int val) {
        assert(val2idx.find(val) != val2idx.end());
        int idx = val2idx[val];
        idx += n;
        do {
            data[idx].erase(val);
        } while (idx >>= 1);
    }
    int query(int a, int b) {
        // [a,b)
        int vl = 0, vr = 0;
        for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                if (!data[l].empty()) {
                    vl = max(vl, *data[l].begin());
                }
                l++;
            }
            if (r & 1) {
                --r;
                if (!data[r].empty()) {
                    vr = max(*data[r].begin(), vr);
                }
            }
        }
        return max(vl, vr);
    }
};
struct HLDecomposition {
    using pii = pair<int, int>;
    int n;
    Graph G;
    vector<int> vid, inv, par, depth, subsize, head, prev, next, type;

    HLDecomposition(const Graph& G_) :
        n(G_.size()), G(G_),
        vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
        head(n), prev(n, -1), next(n, -1), type(n) {}
    void build(vector<int> roots = { 0 }) {
        int curtype = 0, pos = 0;
        for (int root : roots) {
            decide_heavy_edge(root);
            reconstruct(root, curtype++, pos);
        }
    }
    void decide_heavy_edge(int root) {
        stack<pii> st;
        par[root] = -1, depth[root] = 0;
        st.emplace(root, 0);
        while (!st.empty()) {
            int now = st.top().first;
            int& way = st.top().second;
            if (way < G[now].size()) {
                int child = G[now][way++];
                if (child == par[now])continue;
                par[child] = now;
                depth[child] = depth[now] + 1;
                st.emplace(child, 0);
            }
            else {
                st.pop();
                int maxsize = 0;
                for (auto child : G[now]) {
                    if (child == par[now])continue;
                    subsize[now] += subsize[child];
                    if (maxsize < subsize[child]) {
                        maxsize = subsize[child];
                        prev[child] = now;
                        next[now] = child;
                    }
                }
            }
        }
    }
    void reconstruct(int root, int curtype, int& pos) {
        stack<int> st({ root });
        while (!st.empty()) {
            int start = st.top(); st.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto child : G[v]) {
                    if (child != par[v] && child != next[v]) {
                        st.push(child);
                    }
                }
            }
        }
    }

    // node query [u, v], f([left, right])
    void foreach_nodes(int u, int v, const function<void(int, int)>& f) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v])v = par[head[v]];
            else break;
        }
    }

    // edge query[u,v] f([left, right])
    // seg_node[vid[i]] := edge(par[i] -> i)
    void foreach_edges(int u, int v, const function<void(int, int)>& f) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            }
            else {
                if (u != v)f(vid[u] + 1, vid[v]);
                break;
            }
        }
    }
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v])swap(u, v);
            if (head[u] == head[v])return u;
            v = par[head[v]];
        }
    }
};

int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;
    Graph graph(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    TwoEdgeConnectedComponents tecc(graph);
    const auto& trans = tecc.trans;
    const auto& ngraph = tecc.ngraph;

    HLDecomposition hld(ngraph); hld.build();
    SegmentTree seg; seg.init(trans.size());
    rep(q, Q) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, w;
            cin >> u >> w;
            u--;

            u = trans[u];
            u = hld.vid[u];
            seg.add_val(u, w);
        }
        else {
            int s, t;
            cin >> s >> t;
            s--; t--;

            s = trans[s];
            t = trans[t];
            int res = 0;
            hld.foreach_nodes(s, t, [&](int l, int r) {
                res = max(res, seg.query(l, r + 1));
            });
            if (res == 0) {
                cout << -1 << endl;
            }
            else {
                seg.erase_val(res);
                cout << res << endl;
            }
        }
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード