結果
問題 | No.1054 Union add query |
ユーザー | QCFium |
提出日時 | 2019-11-03 11:29:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 1,512 ms |
コンパイル使用メモリ | 172,744 KB |
実行使用メモリ | 35,200 KB |
最終ジャッジ日時 | 2024-05-05 22:31:00 |
合計ジャッジ時間 | 4,274 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 74 ms
10,812 KB |
testcase_04 | AC | 152 ms
35,200 KB |
testcase_05 | AC | 61 ms
7,040 KB |
testcase_06 | AC | 68 ms
16,808 KB |
testcase_07 | AC | 63 ms
16,940 KB |
testcase_08 | AC | 62 ms
16,936 KB |
testcase_09 | AC | 100 ms
34,552 KB |
testcase_10 | AC | 63 ms
34,560 KB |
ソースコード
#include <bits/stdc++.h> #ifdef WIN32 #define getchar_fast _getchar_nolock #else #define getchar_fast getchar_unlocked #endif int ri() { int r = 0, c, s = 0; for (;;) { c = getchar(); if (c == '-') { s = 1; break; } if (c >= '0' && c <= '9') { r = c - '0'; break; } } for (;;) { c = getchar(); if (c < '0' || c > '9') break; r = r * 10 + c - '0'; } return s ? -r : r; } 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; }