結果
問題 |
No.1054 Union add query
|
ユーザー |
|
提出日時 | 2020-07-05 16:11:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 428 ms / 2,000 ms |
コード長 | 1,286 bytes |
コンパイル時間 | 3,096 ms |
コンパイル使用メモリ | 194,012 KB |
最終ジャッジ日時 | 2025-01-11 15:58:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> val(n); vector<int> par(n); vector<int> siz(n); for (int i = 0; i < n; i++) { par[i] = i; siz[i] = 1; } while (q--) { int t, a, b; cin >> t >> a >> b; // cerr << endl; // cerr << "type = " << t << " a = " << a << " b = " << b << endl; a--; b--; if (t == 1) { while (par[a] != a) a = par[a]; while (par[b] != b) b = par[b]; if (siz[a] > siz[b]) swap(a, b); if (a == b) continue; siz[b] += siz[a]; val[a] -= val[b]; par[a] = b; //cerr << "a = " << a + 1 << " b = " << b << endl; //cerr << "val[a] = " << val[a] << " val[b] = " << val[b] << endl; } if (t == 2) { while (par[a] != a) a = par[a]; b++; val[a] += b; //cerr << "val[a] = " << val[a] << endl; } if (t == 3) { int ans = val[a]; //cerr << "ans = " << ans << endl; while (par[a] != a) { a = par[a]; ans += val[a]; // cerr << "a = " << a << " val[a] = " << val[a] << endl; // cerr << "ans = " << ans << endl; } cout << ans << '\n'; } } return 0; }