結果
問題 | No.1054 Union add query |
ユーザー | QCFium |
提出日時 | 2019-11-03 11:25:56 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 265 ms / 2,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 1,499 ms |
コンパイル使用メモリ | 172,628 KB |
実行使用メモリ | 35,328 KB |
最終ジャッジ日時 | 2024-05-05 22:31:05 |
合計ジャッジ時間 | 4,337 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 185 ms
10,880 KB |
testcase_04 | AC | 265 ms
35,328 KB |
testcase_05 | AC | 165 ms
7,040 KB |
testcase_06 | AC | 173 ms
16,940 KB |
testcase_07 | AC | 162 ms
16,936 KB |
testcase_08 | AC | 170 ms
17,064 KB |
testcase_09 | AC | 208 ms
34,560 KB |
testcase_10 | AC | 155 ms
34,688 KB |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } struct QuickFind { std::vector<int> parent; // -size if it's root std::vector<std::vector<int> > child; std::vector<int> plus; QuickFind (int n) : parent(n, -1), child(n), plus(n) { for (int i = 0; i < n; i++) child[i].push_back(i); } int root(int i) { return parent[i] < 0 ? i : parent[i] = root(parent[i]); } void add_union(int i, int val) { plus[root(i)] += val; } int get(int i) { return parent[i] < 0 ? plus[i] : plus[i] + plus[root(i)]; } void unite(int i, int j) { i = root(i); j = root(j); if (i == j) return; if (parent[i] > parent[j]) std::swap(i, j); parent[i] += parent[j]; parent[j] = i; int sub = plus[j] - plus[i]; plus[j] = 0; for (auto k : child[j]) { child[i].push_back(k); plus[k] += sub; } child[j].clear(); } }; int main() { int n = ri(); int q = ri(); QuickFind uni(n); for (int i = 0; i < q; i++) { int t = ri(), a = ri() - 1, b = ri(); if (t == 1) uni.unite(a, b - 1); else if (t == 2) uni.add_union(a, b); else printf("%d\n", uni.get(a)); } return 0; }