結果
問題 | No.2296 Union Path Query (Hard) |
ユーザー | 👑 Nachia |
提出日時 | 2024-04-23 01:20:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 213 ms / 7,000 ms |
コード長 | 6,720 bytes |
コンパイル時間 | 1,576 ms |
コンパイル使用メモリ | 99,528 KB |
実行使用メモリ | 15,832 KB |
最終ジャッジ日時 | 2024-10-15 00:34:45 |
合計ジャッジ時間 | 15,739 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 10 ms
13,440 KB |
testcase_02 | AC | 9 ms
13,440 KB |
testcase_03 | AC | 10 ms
13,440 KB |
testcase_04 | AC | 122 ms
14,680 KB |
testcase_05 | AC | 131 ms
14,808 KB |
testcase_06 | AC | 159 ms
14,684 KB |
testcase_07 | AC | 149 ms
15,708 KB |
testcase_08 | AC | 145 ms
15,580 KB |
testcase_09 | AC | 135 ms
10,308 KB |
testcase_10 | AC | 135 ms
10,308 KB |
testcase_11 | AC | 133 ms
10,180 KB |
testcase_12 | AC | 131 ms
9,444 KB |
testcase_13 | AC | 92 ms
5,248 KB |
testcase_14 | AC | 85 ms
5,248 KB |
testcase_15 | AC | 163 ms
15,832 KB |
testcase_16 | AC | 163 ms
12,140 KB |
testcase_17 | AC | 124 ms
6,400 KB |
testcase_18 | AC | 213 ms
15,580 KB |
testcase_19 | AC | 178 ms
9,572 KB |
testcase_20 | AC | 208 ms
15,708 KB |
testcase_21 | AC | 199 ms
15,712 KB |
testcase_22 | AC | 201 ms
15,580 KB |
testcase_23 | AC | 118 ms
15,700 KB |
testcase_24 | AC | 104 ms
9,440 KB |
testcase_25 | AC | 97 ms
14,808 KB |
testcase_26 | AC | 96 ms
14,808 KB |
testcase_27 | AC | 131 ms
14,804 KB |
testcase_28 | AC | 129 ms
14,808 KB |
testcase_29 | AC | 131 ms
15,576 KB |
testcase_30 | AC | 134 ms
15,704 KB |
testcase_31 | AC | 146 ms
15,828 KB |
testcase_32 | AC | 149 ms
15,704 KB |
testcase_33 | AC | 160 ms
15,320 KB |
testcase_34 | AC | 126 ms
14,812 KB |
testcase_35 | AC | 125 ms
14,688 KB |
testcase_36 | AC | 183 ms
14,296 KB |
testcase_37 | AC | 154 ms
12,208 KB |
testcase_38 | AC | 155 ms
12,172 KB |
testcase_39 | AC | 152 ms
12,212 KB |
testcase_40 | AC | 157 ms
12,596 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 141 ms
15,636 KB |
testcase_45 | AC | 143 ms
15,520 KB |
testcase_46 | AC | 148 ms
15,704 KB |
testcase_47 | AC | 149 ms
15,708 KB |
testcase_48 | AC | 151 ms
15,708 KB |
ソースコード
#include <vector>#include <algorithm>namespace nachia {struct IncrementalForest{struct Node {int jump;int parent;int parentEdge;int depth;int child;int brother;};std::vector<Node> nodes;std::vector<int> dsu;std::vector<bool> todbl;int edgeIndex;void makeToDbl(int x){while(int(todbl.size()) < x){int z = int(todbl.size());todbl.resize(z*2+1);std::copy(todbl.begin(), todbl.begin() + z, todbl.begin() + z);todbl[z*2] = true;}}IncrementalForest(int n = 0){nodes.assign(n, { -1, -1, -1, 0, -1, -1 });dsu.assign(n, -1);todbl.assign(1, false);makeToDbl(n);edgeIndex = 0;}int rootOf(int u){if(dsu[u] < 0) return u;return dsu[u] = rootOf(dsu[u]);}bool areConnected(int u, int v){ return rootOf(u) == rootOf(v); }int componentSize(int u){ return -dsu[rootOf(u)]; }int numVertices(){ return nodes.size(); }int addNode(){int v = numVertices();nodes.push_back({ -1, -1, -1, 0, -1, -1 });makeToDbl(numVertices());return v;}int addEdge(int u, int v){std::vector<int> bfs;{int ru = rootOf(u);int rv = rootOf(v);if(ru == rv) return -1;if(-dsu[ru] < -dsu[rv]){ std::swap(u, v); std::swap(ru, rv); }bfs = std::vector<int>(-dsu[rv]);dsu[ru] += dsu[rv];dsu[rv] = ru;}int e = edgeIndex++;int bfsp = 0;auto setParent = [&](int v, int p) -> void {nodes[v].parent = p;nodes[v].depth = nodes[p].depth + 1;nodes[v].jump = todbl[nodes[v].depth - 1] ? nodes[nodes[p].jump].jump : p;};int p = u;int p2 = v;for(int x=nodes[v].child; x>=0; x=nodes[x].brother) bfs[bfsp++] = x;while(nodes[p2].parent >= 0){int w = nodes[p2].parent;for(int *pc=&nodes[w].child; *pc>=0; ){int x = *pc;if(x == p2){*pc = nodes[x].brother;std::swap(nodes[p2].parentEdge, e);nodes[p2].brother = nodes[p].child;nodes[p].child = p2;setParent(p2, p);} else {bfs[bfsp++] = x;pc = &nodes[x].brother;}}p = p2; p2 = w;}std::swap(nodes[p2].parentEdge, e);nodes[p2].brother = nodes[p].child;nodes[p].child = p2;setParent(p2, p);for(int i=0; i<bfsp; i++){int w = bfs[i];setParent(w, nodes[w].parent);for(int x=nodes[w].child; x>=0; x=nodes[x].brother) bfs[bfsp++] = x;}return edgeIndex - 1;}int parentOf(int u){ return nodes[u].parent; }int parentEdgeOf(int u){ return nodes[u].parentEdge; }int depth(int u){ return nodes[u].depth; }int lca(int u, int v){if(!areConnected(u, v)) return -1;if(depth(u) < depth(v)) std::swap(u, v);int dv = depth(v);while(depth(u) != dv){u = (depth(nodes[u].jump) >= dv ? nodes[u].jump : nodes[u].parent);}while(u != v){if(nodes[u].jump != nodes[v].jump){u = nodes[u].jump;v = nodes[v].jump;} else {u = nodes[u].parent;v = nodes[v].parent;}}return u;}int middle(int u, int v, int w){if(!areConnected(u, v) || !areConnected(v, w)) return -1;return lca(u,v) ^ lca(v,w) ^ lca(w,u);}int dist(int u, int v){if(!areConnected(u, v)) return -1;return depth(u) - depth(lca(u, v)) * 2 + depth(v);}struct ChildrenIterRange {struct Iter {std::vector<Node>::iterator nodes; int v;int operator*() const { return v; }Iter& operator++(){ v = nodes[v].brother; return *this; }Iter operator++(int) const { auto a = *this; return ++a; }bool operator==(Iter& r) const { return v == r.v; }bool operator!=(Iter& r) const { return v != r.v; }};std::vector<Node>::iterator nodes; int v;Iter begin() const { return { nodes, nodes[v].child }; }Iter end() const { return { nodes, -1 }; }};ChildrenIterRange children(int v){return ChildrenIterRange{ nodes.begin(), v };}};} // namespace nachia#include <iostream>#include <string>int main(){using namespace std;ios::sync_with_stdio(false); cin.tie(nullptr);int N, X, Q; cin >> N >> X >> Q;nachia::IncrementalForest forest(N);std::vector<long long> depth(N);std::vector<long long> weight;struct Diam { long long d; int v; int w; };std::vector<Diam> diam(N);for(int i=0; i<N; i++) diam[i] = { 0,i,i };auto dist = [&](int u, int v) -> long long {int g = forest.lca(u, v);if(g < 0) return -1;long long d = depth[u] - 2 * depth[g] + depth[v];return d;};auto mergeDiam = [&](Diam l, Diam r) -> Diam {Diam res = l;if(res.d < r.d) res = r;auto upd = [&](int v, int w){long long d = dist(v,w);if(res.d < d) res = { d,v,w };};upd(l.v, r.v);upd(l.v, r.w);upd(l.w, r.v);upd(l.w, r.w);return res;};for(int qi=0; qi<Q; qi++){int t; cin >> t;if(t == 1){int v, w; cin >> v >> w;int u = X;int ur = forest.rootOf(u);int vr = forest.rootOf(v);if(forest.addEdge(u, v) < 0) exit(1);int xr = forest.rootOf(v);weight.push_back(w);if(forest.parentOf(v) != u) std::swap(u, v);auto dfs = [&](auto& dfs, int x) -> void {depth[x] = depth[forest.parentOf(x)] + weight[forest.parentEdgeOf(x)];for(int y : forest.children(x)) dfs(dfs, y);};dfs(dfs, v);diam[xr] = mergeDiam(diam[ur], diam[vr]);}if(t == 2){int u, v; cin >> u >> v;long long d = dist(u, v);cout << d << '\n';if(d != -1) X = (X + d) % N;}if(t == 3){int v; cin >> v;cout << diam[forest.rootOf(v)].d << '\n';}if(t == 4){int v; cin >> v;X = (X + v) % N;}}return 0;}