結果

問題 No.529 帰省ラッシュ
ユーザー nanophoto12nanophoto12
提出日時 2021-05-05 21:11:46
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,636 bytes
コンパイル時間 5,088 ms
コンパイル使用メモリ 289,132 KB
実行使用メモリ 58,696 KB
最終ジャッジ日時 2023-10-11 15:15:26
合計ジャッジ時間 13,418 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 1 ms
4,352 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 440 ms
20,564 KB
testcase_13 AC 626 ms
58,696 KB
testcase_14 AC 506 ms
23,368 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 512 ms
36,688 KB
testcase_18 AC 513 ms
37,172 KB
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

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

template<typename T>
void chmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void chmaxmap(map<T, T>& m, T key, T value) {
	if (m.count(key)) {
		chmax(m[key], value);
	}
	else {
		m[key] = value;
	}
}

template<typename T>
void chmin(T& reference, T value) {
	reference = min(reference, value);
}

#include <atcoder/all>

using namespace atcoder;

typedef modint1000000007 mint;

template< typename G >
struct HeavyLightDecomposition {
    G& g;
    vector< int > sz, in, out, head, rev, par;

    HeavyLightDecomposition(G& g) :
        g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

    void dfs_sz(int idx, int p) {
        par[idx] = p;
        sz[idx] = 1;
        if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
        for (auto& to : g[idx]) {
            if (to == p) continue;
            dfs_sz(to, idx);
            sz[idx] += sz[to];
            if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
        }
    }

    void dfs_hld(int idx, int par, int& times) {
        in[idx] = times++;
        rev[in[idx]] = idx;
        for (auto& to : g[idx]) {
            if (to == par) continue;
            head[to] = (g[idx][0] == to ? head[idx] : to);
            dfs_hld(to, idx, times);
        }
        out[idx] = times;
    }

    void build() {
        dfs_sz(0, -1);
        int t = 0;
        dfs_hld(0, -1, t);
    }

    int la(int v, int k) {
        while (1) {
            int u = head[v];
            if (in[v] - k >= in[u]) return rev[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
    }

    int lca(int u, int v) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }

    template< typename T, typename Q, typename F >
    T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) {
        T l = ti, r = ti;
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v), swap(l, r);
            if (head[u] == head[v]) break;
            l = f(q(in[head[v]], in[v] + 1), l);
        }
        return f(f(q(in[u] + edge, in[v] + 1), l), r);
    }

    template< typename Q >
    void add(int u, int v, const Q& q, bool edge = false) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) break;
            q(in[head[v]], in[v] + 1);
        }
        q(in[u] + edge, in[v] + 1);
    }
};

typedef vector<vector<int>> UnWeightedGraph;

class lca {
public:
    typedef vector<vector<int>> Graph;
    const int n;
    const int log2_n;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth;

    lca(const Graph& g, int root)
        : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) {
        dfs(g, root, -1, 0);
        for (int k = 0; k + 1 < log2_n; k++) {
            for (int v = 0; v < (int)g.size(); v++) {
                if (parent[k][v] < 0)
                    parent[k + 1][v] = -1;
                else
                    parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }

    void dfs(const Graph& g, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (int j = 0; j < g[v].size(); j++) {
            if (g[v][j] != p) dfs(g, g[v][j], v, d + 1);
        }
    }

    int get(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int k = 0; k < log2_n; k++) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = log2_n - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

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

};

namespace {
    using namespace std;

    template< typename G >
    struct LowLink {
        const G& g;
        vector< int > used, ord, low;
        vector< int > articulation;
        vector< pair< int, int > > bridge;

        LowLink(const G& g) : g(g) {}

        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 (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, (int)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;
        }

        virtual void build() {
            used.assign(g.size(), 0);
            ord.assign(g.size(), 0);
            low.assign(g.size(), 0);
            int k = 0;
            for (int i = 0; i < g.size(); i++) {
                if (!used[i]) k = dfs(i, k, -1);
            }
        }
    };

    template< typename G >
    struct TwoEdgeConnectedComponents {
        vector< int > comp;
        LowLink< G > lowLink_;
        TwoEdgeConnectedComponents(const G& g) : lowLink_(g) {}

        int operator[](const int& k) {
            return comp[k];
        }

        void dfs(int idx, int par, int& k) {
            if (~par && lowLink_.ord[par] >= lowLink_.low[idx]) comp[idx] = comp[par];
            else comp[idx] = k++;
            for (auto& to : lowLink_.g[idx]) {
                if (comp[to] == -1) dfs(to, idx, k);
            }
        }

        typedef std::vector<std::vector<int>> UnWeightedGraph;

        void build(UnWeightedGraph& t) {
            lowLink_.build();
            comp.assign(lowLink_.g.size(), -1);
            int k = 0;
            for (int i = 0; i < comp.size(); i++) {
                if (comp[i] == -1) dfs(i, -1, k);
            }
            t.resize(k);
            for (auto& e : lowLink_.bridge) {
                int x = comp[e.first], y = comp[e.second];
                t[x].push_back(y);
                t[y].push_back(x);
            }
        }
    };
}

ll op(ll left, ll right) {
    return max(left, right);
}

ll e() { return -1; }

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    typedef vector<vector<int>> G;
    TwoEdgeConnectedComponents<G> comp(g);
    G links;
    comp.build(links);
    HeavyLightDecomposition<G> hld(links);
    hld.build();
    vector<set<ll>> monstors(links.size());
    segtree<ll, op, e> all(links.size());
    rep(i, links.size()) all.set(i, -1);
    map<ll, int> vToId;
    vector<ll> ans;
    rep(_, q) {
        ll args, u, v;
        cin >> args >> u >> v;
        if (args == 1) {
            u--;
            int id = comp.comp[u];
            monstors[id].insert(v);
            vToId[v] = id;
            if (all.get(id) < v) {
                all.set(id, v);
            }
        }
        else {
            u--; v--;
            int id1 = comp.comp[u];
            int id2 = comp.comp[v];
            ll t = hld.query(id1, id2, -1LL, [&](int x, int y) {
                return all.prod(x, y);
                }, [&](ll x, ll y) {
                    return max(x, y);
                });
            ans.push_back(t);
            if (t != -1) {
                int id = vToId[t];
                monstors[id].erase(t);
                vToId.erase(t);
                if (monstors[id].size()) {
                    all.set(id, *monstors[id].rbegin());
                }
                else {
                    all.set(id, -1);
                }
            }
        }
    }
    for (auto x : ans) {
        cout << x << endl;
    }        
    return 0;
}
0