結果
問題 | No.1054 Union add query |
ユーザー |
|
提出日時 | 2020-05-15 23:59:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 2,201 bytes |
コンパイル時間 | 1,713 ms |
コンパイル使用メモリ | 175,580 KB |
実行使用メモリ | 40,960 KB |
最終ジャッジ日時 | 2024-09-19 14:40:17 |
合計ジャッジ時間 | 4,332 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr char newl = '\n'; struct UnionFind { //各要素が属する集合の代表(根)を管理する //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい vector<int> data; UnionFind(int sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x); y = find(y); bool is_union = (x != y); if (is_union) { if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; } return is_union; } int find(int x) { if (data[x] < 0) { //要素xが根である return x; } else { data[x] = find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される return data[x]; } } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -data[find(x)]; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; UnionFind uf(n); vector<ll> data(n, 0); vector<ll> lazy(n, 0); vector< vector<int> > memo(n); for (int i = 0; i < n; i++) { memo[i].push_back(i); } for (int i = 0; i < q; i++) { int t, a, b; cin >> t >> a >> b; --a; if (t == 1) { --b; if (uf.same(a, b)) continue; int ra = uf.find(a); int rb = uf.find(b); uf.unite(a, b); int root = uf.find(a); if (root == rb) { swap(a, b); swap(ra, rb); } lazy[rb] -= lazy[ra]; for (int j : memo[rb]) { memo[ra].push_back(j); data[j] += lazy[rb]; } lazy[rb] = 0; } else if (t == 2) { int root = uf.find(a); lazy[root] += b; } else { int root = uf.find(a); cout << data[a] + lazy[root] << newl; } } return 0; }