結果
問題 | No.1054 Union add query |
ユーザー |
![]() |
提出日時 | 2020-05-15 22:22:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 849 ms / 2,000 ms |
コード長 | 2,788 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 101,872 KB |
実行使用メモリ | 150,056 KB |
最終ジャッジ日時 | 2024-09-19 11:09:31 |
合計ジャッジ時間 | 5,717 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} class DisjointSet{ public: vector<int> rank,p; vector<int> sz; DisjointSet(){} DisjointSet(int size){ rank.resize(size,0); p.resize(size,0); sz.resize(size,0); for(int i=0;i<size;i++) makeSet(i); } void makeSet(int x){ p[x]=x; rank[x]=0; sz[x]=1; } bool same(int x,int y){ return findSet(x)==findSet(y); } void unite(int x,int y){ if(same(x,y)) return; link(findSet(x),findSet(y)); } void link(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; sz[x]+=sz[y]; }else{ p[x]=y; sz[y]+=sz[x]; if(rank[x]==rank[y]){ rank[y]++; } } } int findSet(int x){ if(x!=p[x]){ p[x]=findSet(p[x]); } return p[x]; } int findSize(int x){ return sz[findSet(x)]; } }; int main(){ int N,Q; scanf("%d %d",&N,&Q); vector<vector<int>> addTimes(N),sum(N); rep(i,N){ addTimes[i].push_back(-1); sum[i].push_back(0); } DisjointSet us(N); vector<vector<int>> changeTimes(N),leader(N); rep(i,N){ leader[i].push_back(i); changeTimes[i].push_back(0); } vector<vector<int>> state(N); rep(i,N) state[i].push_back(i); for(int q=1;q<=Q;q++){ int T,A,B; scanf("%d %d %d",&T,&A,&B); if(T==1){ A--;B--; if(us.same(A,B)) continue; int preA=us.findSet(A); int preB=us.findSet(B); us.unite(A,B); int target=us.findSet(A); if(preA!=target) swap(preA,preB); for(auto n:state[preB]){ changeTimes[n].push_back(q); leader[n].push_back(target); state[target].push_back(n); } state[preB].clear(); }else if(T==2){ A--; int target=us.findSet(A); addTimes[target].push_back(q); int s=sum[target].back(); sum[target].push_back(s+B); }else if(T==3){ A--; int ed=q; int ans=0; for(int i=leader[A].size()-1;i>=0;i--){ int st=changeTimes[A][i]; int target=leader[A][i]; int r=lower_bound(addTimes[target].begin(),addTimes[target].end(),ed)-addTimes[target].begin(); int l=lower_bound(addTimes[target].begin(),addTimes[target].end(),st)-addTimes[target].begin(); r--;l--; ans+=sum[target][r]-sum[target][l]; ed=st; } printf("%d\n",ans); } } return 0; }