結果
問題 |
No.1054 Union add query
|
ユーザー |
![]() |
提出日時 | 2023-03-14 12:48:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 617 ms / 2,000 ms |
コード長 | 1,512 bytes |
コンパイル時間 | 3,699 ms |
コンパイル使用メモリ | 250,436 KB |
最終ジャッジ日時 | 2025-02-11 11:07:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=int; using ld=long double; ld pie=3.141592653589793; ll inf=15555055; ll mod=998244353; int main(){ ll n,q; cin >> n >> q; vector<ll>oya(n),siz(n,1),now(n,0); for (ll i = 0; i < n; i++) { oya[i]=i; } vector<ll>aa; for (ll i = 0; i < q; i++) { ll t,a,b; cin >> t >> a >> b; if (t==1) { a--,b--; while (oya[a]!=a) { a=oya[a]; } while (oya[b]!=b) { b=oya[b]; } if (a==b) { continue; } if (siz[a]>=siz[b]) { siz[a]=max(siz[a],siz[b]+1); oya[b]=a; now[b]-=now[a]; }else{ siz[b]=max(siz[b],siz[a]+1); oya[a]=b; now[a]-=now[b]; } }else if (t==2) { a--; while (a!=oya[a]) { a=oya[a]; } now[a]+=b; }else{ a--; ll ans=0; while (a!=oya[a]) { ans+=now[a]; a=oya[a]; } ans+=now[a]; aa.push_back(ans); } } for (ll i = 0; i < aa.size(); i++) { cout << aa[i] << endl; } }