結果
問題 | No.1054 Union add query |
ユーザー |
![]() |
提出日時 | 2020-05-15 21:48:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 2,813 ms |
コンパイル使用メモリ | 194,736 KB |
最終ジャッジ日時 | 2025-01-10 11:29:56 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;} template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;} #define fr(i,n) for(int i=0;i<(n);++i) #define Fr(i,n) for(int i=1;i<=(n);++i) #define ifr(i,n) for(int i=(n)-1;i>=0;--i) #define iFr(i,n) for(int i=(n);i>0;--i) struct UF{ vector<int> par,sz,X; explicit UF(int n):par(n),sz(n,1),X(n){ iota(par.begin(),par.end(),0); } int find(int x){ if(par[x]==x) return x; return find(par[x]); } bool unit(int x, int y){ x=find(x); y=find(y); if(x==y) return false; if(sz[x]>sz[y]){ par[y]=x; sz[x]+=sz[y]; X[y]-=X[x]; } else{ par[x]=y; sz[y]+=sz[x]; X[x]-=X[y]; } return true; } bool same(int x, int y){return find(x)==find(y);} int q(int x){ int s{X[x]}; while(x!=par[x]) x=par[x],s+=X[x]; return s; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,q; cin>>n>>q; UF uf(n); fr(i,q){ int t,a,b; cin>>t>>a>>b;--a; if(t==1) uf.unit(a,b-1); else if(t==2) uf.X[uf.find(a)]+=b; else cout<<uf.q(a)<<'\n'; } }