結果
問題 | No.1054 Union add query |
ユーザー | wk |
提出日時 | 2020-05-16 14:09:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,058 bytes |
コンパイル時間 | 1,552 ms |
コンパイル使用メモリ | 171,656 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-09-22 07:54:54 |
合計ジャッジ時間 | 7,159 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 578 ms
6,940 KB |
testcase_07 | AC | 543 ms
6,940 KB |
testcase_08 | AC | 481 ms
6,940 KB |
testcase_09 | AC | 731 ms
9,216 KB |
testcase_10 | AC | 280 ms
9,088 KB |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0; (i) < (n); (i)++)using namespace std;long modpow(long a, long n, long mod) {long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}// a^{-1} mod を計算するlong modinv(long a, long mod) {return modpow(a, mod - 2, mod);}int GCD(int a, int b){if(b == 0) return a;if(a < b) return GCD(b, a);else return GCD(b, a%b);}struct UnionFind {vector<int> par;vector<int> rank;UnionFind(int n = 1){init(n);}void init(int n = 1){par.resize(n);rank.resize(n);REP(i, n) par[i] = i, rank[i] = 0;}int root(int x){if(par[x] == x) return x;else return par[x] = root(par[x]);}bool issame(int x, int y){return root(x) == root(y);}void merge(int x, int y){x = root(x); y = root(y);if(x == y) return;if(rank[x] < rank[y]) swap(x, y);if(rank[x] == rank[y]) rank[x]++;par[y] = x;return;}};int main(){int N, Q; cin >> N >> Q;UnionFind uf(N);int num[500005];REP(i, N) num[i] = 0;REP(i, Q){//REP(i, N) cout << num[i] << " ";//cout << endl;int T, A, B; cin >> T >> A >> B;if(T==1){int nea = uf.root(A-1);int neb = uf.root(B-1);if(nea != neb){uf.merge(A-1, B-1);if(uf.root(A-1) == nea){num[neb] -= num[nea];}else{num[nea] -= num[neb];}}}else if(T==2){num[uf.root(A-1)] += B;}else{int sum = 0;int first = A-1;for(;;){sum += num[first];if(first == uf.par[first]) break;first = uf.par[first];}cout << sum << endl;}}return 0;}