結果
問題 |
No.1054 Union add query
|
ユーザー |
![]() |
提出日時 | 2025-07-26 16:57:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,000 bytes |
コンパイル時間 | 3,104 ms |
コンパイル使用メモリ | 279,828 KB |
実行使用メモリ | 8,960 KB |
最終ジャッジ日時 | 2025-07-26 16:59:44 |
合計ジャッジ時間 | 6,259 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, q; cin >> n >> q; mt19937_64 mt((size_t)main); vector<int> par(n), pr(n), data(n); for (int i = 0; i < n; i++) { par[i] = i; pr[i] = (int)mt(); } auto find = [&](int v) { while (v != par[v]) v = par[v]; return v; }; auto merge = [&](int u, int v) { u = find(u), v = find(v); if (u == v) return; if (pr[u] < pr[v]) swap(u, v); par[v] = u; data[v] -= data[u]; }; auto get_data = [&](int v) -> int { int ret = data[v]; while (v != par[v]) ret += data[v = par[v]]; return ret; }; while (q--) { int t, a, b; cin >> t >> a >> b; if (t == 1) { merge(a - 1, b - 1); } else if (t == 2) { data[find(a - 1)] += b; } else { cout << get_data(a - 1) << "\n"; } } }