結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー | t98slider |
提出日時 | 2023-02-15 08:57:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 859 ms / 7,000 ms |
コード長 | 5,124 bytes |
コンパイル時間 | 2,756 ms |
コンパイル使用メモリ | 205,268 KB |
実行使用メモリ | 67,532 KB |
最終ジャッジ日時 | 2024-05-02 13:57:08 |
合計ジャッジ時間 | 30,095 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 42 ms
54,724 KB |
testcase_02 | AC | 42 ms
54,856 KB |
testcase_03 | AC | 42 ms
54,856 KB |
testcase_04 | AC | 289 ms
58,704 KB |
testcase_05 | AC | 283 ms
58,704 KB |
testcase_06 | AC | 408 ms
61,008 KB |
testcase_07 | AC | 439 ms
62,540 KB |
testcase_08 | AC | 439 ms
62,540 KB |
testcase_09 | AC | 335 ms
36,768 KB |
testcase_10 | AC | 334 ms
36,772 KB |
testcase_11 | AC | 348 ms
36,768 KB |
testcase_12 | AC | 328 ms
32,676 KB |
testcase_13 | AC | 108 ms
5,888 KB |
testcase_14 | AC | 98 ms
5,376 KB |
testcase_15 | AC | 454 ms
62,032 KB |
testcase_16 | AC | 421 ms
47,968 KB |
testcase_17 | AC | 212 ms
17,464 KB |
testcase_18 | AC | 617 ms
63,948 KB |
testcase_19 | AC | 409 ms
32,932 KB |
testcase_20 | AC | 604 ms
63,948 KB |
testcase_21 | AC | 556 ms
62,160 KB |
testcase_22 | AC | 548 ms
61,772 KB |
testcase_23 | AC | 279 ms
64,160 KB |
testcase_24 | AC | 222 ms
32,596 KB |
testcase_25 | AC | 304 ms
65,868 KB |
testcase_26 | AC | 299 ms
65,868 KB |
testcase_27 | AC | 783 ms
65,872 KB |
testcase_28 | AC | 786 ms
65,996 KB |
testcase_29 | AC | 843 ms
67,532 KB |
testcase_30 | AC | 859 ms
67,400 KB |
testcase_31 | AC | 854 ms
62,924 KB |
testcase_32 | AC | 793 ms
62,416 KB |
testcase_33 | AC | 727 ms
61,516 KB |
testcase_34 | AC | 511 ms
60,236 KB |
testcase_35 | AC | 478 ms
59,728 KB |
testcase_36 | AC | 409 ms
57,928 KB |
testcase_37 | AC | 742 ms
44,532 KB |
testcase_38 | AC | 750 ms
42,860 KB |
testcase_39 | AC | 775 ms
44,408 KB |
testcase_40 | AC | 757 ms
44,280 KB |
testcase_41 | AC | 2 ms
5,376 KB |
testcase_42 | AC | 2 ms
5,376 KB |
testcase_43 | AC | 2 ms
5,376 KB |
testcase_44 | AC | 553 ms
64,584 KB |
testcase_45 | AC | 570 ms
64,332 KB |
testcase_46 | AC | 573 ms
65,612 KB |
testcase_47 | AC | 571 ms
66,640 KB |
testcase_48 | AC | 582 ms
65,224 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class S, S (*op)(S, S), S (*e)()> struct Multiple_LCA_Tree{ int MAX_LOGV, N; std::vector<std::vector<std::pair<int, S>>> G; //重み付きグラフ std::vector<std::vector<int>> parent; //親の頂点のダブリング配列 std::vector<std::vector<S>> dp; //辺の重みのダブリング配列 std::vector<int> depth; //連結成分の代表元からの深さ std::vector<int> parent_or_size; //Union Find std::vector<std::tuple<S, int, int>> diameter_and_vertex; //直径と頂点を入れる std::queue<int> que; //BFS用 Multiple_LCA_Tree(int _n) : N(_n){ MAX_LOGV = std::__lg(N) + 1; G.resize(N); parent.resize(MAX_LOGV, std::vector<int>(N, -1)); dp.resize(MAX_LOGV, std::vector<S>(N, e())); depth.resize(N); parent_or_size.resize(N, -1); diameter_and_vertex.resize(N); for(int i = 0; i < N; i++) diameter_and_vertex[i] = std::make_tuple(0, i, i); } int leader(int v){ if(parent_or_size[v] < 0) return v; return parent_or_size[v] = leader(parent_or_size[v]); } //頂点uと頂点vを重さwの辺で結ぶ void merge(int u, int v, S w){ int x = leader(u), y = leader(v); if(x == y) return; if(-parent_or_size[x] < -parent_or_size[y]) { std::swap(x, y); std::swap(u, v); } //x-u の連結成分側を親とする parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; //辺を追加してDFSでダブリングを更新 G[u].emplace_back(v, w); G[v].emplace_back(u, w); int lim_logv = std::__lg(-parent_or_size[x]) + 1; register_parent(v, u, w); que.push(v); while(!que.empty()){ v = que.front(); update_dp_table(v, lim_logv); que.pop(); for(auto &edge : G[v]){ std::tie(u, w) = edge; if(parent[0][v] == u) continue; register_parent(u, v, w); que.push(u); } } update_diameter(x, y); } S dist(int u, int v){ if(leader(u) != leader(v)) return -1ll; if(depth[u] > depth[v]) std::swap(u, v); S result = e(); //頂点 v を頂点 u と高さが同じになるようにする for(int i = 0; i < MAX_LOGV; i++){ if((depth[v] - depth[u]) >> i & 1){ result = op(result, dp[i][v]); v = parent[i][v]; } } if(u == v) return result; for(int i = MAX_LOGV - 1; i >= 0; i--){ if(parent[i][u] != parent[i][v]){ result = op(result, dp[i][u]); result = op(result, dp[i][v]); u = parent[i][u]; v = parent[i][v]; } } result = op(result, dp[0][u]); result = op(result, dp[0][v]); return result; } private: void update_dp_table(int v, int lim_logv){ for(int i = 0; i + 1 < lim_logv; i++){ if(parent[i][v] == -1) { parent[i + 1][v] = -1; dp[i + 1][v] = dp[i][v]; } else { parent[i + 1][v] = parent[i][parent[i][v]]; dp[i + 1][v] = op(dp[i][parent[i][v]], dp[i][v]); } } } void register_parent(int v, int _parent, S weight){ dp[0][v] = weight; depth[v] = depth[_parent] + 1; parent[0][v] = _parent; } //yの連結成分とxの連結成分の直径を更新 void update_diameter(int x, int y){ S temp; std::array<int, 4> candidate_vertex{}; std::tie(temp, candidate_vertex[0], candidate_vertex[1]) = diameter_and_vertex[x]; std::tie(temp, candidate_vertex[2], candidate_vertex[3]) = diameter_and_vertex[y]; std::tuple<S, int, int> result = std::max(diameter_and_vertex[x], diameter_and_vertex[y]); for(int i = 0; i < 2; i++) { int v1 = candidate_vertex[i]; for(int j = 2; j < 4; j++) { int v2 = candidate_vertex[j]; S length = dist(v1, v2); result = std::max(result, std::make_tuple(length, v1, v2)); } } diameter_and_vertex[x] = result; } }; ll op(ll lhs, ll rhs){ return lhs + rhs; } ll e() { return 0ll; } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll N, X, Q; cin >> N >> X >> Q; Multiple_LCA_Tree<ll, op, e> MLT(N); while(Q--){ int type, v, u, w; cin >> type; if(type == 1){ cin >> v >> w; MLT.merge(v, X, w); }else if(type == 2){ cin >> u >> v; ll d = MLT.dist(u, v); cout << d << '\n'; if(d != -1) (X += d) %= N; }else if(type == 3){ cin >> v; cout << get<0>(MLT.diameter_and_vertex[MLT.leader(v)]) << '\n'; }else{ cin >> v; (X += v) %= N; } } }