結果
問題 | No.1054 Union add query |
ユーザー |
![]() |
提出日時 | 2020-05-15 22:47:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 674 ms / 2,000 ms |
コード長 | 1,407 bytes |
コンパイル時間 | 3,921 ms |
コンパイル使用メモリ | 198,508 KB |
最終ジャッジ日時 | 2025-01-10 11:59:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T, class U> using Pa = pair<T, U>; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; class QuickFind{ private: vec<int> G; vec<int> val; vvec<int> comp; public: QuickFind(int N){ G.resize(N); comp.resize(N); val.resize(N); iota(G.begin(),G.end(),0); for(int i=0;i<N;i++) comp[i].push_back(i); } void unite(int x,int y){ x = G[x],y = G[y]; if(is_same_set(x,y)) return ; if(comp[x].size()<comp[y].size()) swap(x,y); int v = val[y]; for(auto& e:comp[y]){ comp[x].push_back(e); G[e] = x; val[e] -= val[x]; if(e!=y) val[e] += v; } comp[y].clear(); } bool is_same_set(int x,int y){return G[x]==G[y];} int getval(int x){return val[x]+val[G[x]]*(G[x]!=x);} int addval(int x,int v){return val[G[x]] += v;} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; QuickFind uf(N); vec<int> now(N); while(Q--){ int t,a,b; cin >> t >> a >> b; a--; if(t==1){ b--; uf.unite(a,b); } if(t==2) uf.addval(a,b); if(t==3){ cout << uf.getval(a) << "\n"; } } }