結果
問題 | No.1054 Union add query |
ユーザー | fura |
提出日時 | 2020-05-15 22:09:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,356 bytes |
コンパイル時間 | 2,618 ms |
コンパイル使用メモリ | 219,116 KB |
実行使用メモリ | 52,404 KB |
最終ジャッジ日時 | 2024-09-19 10:44:07 |
合計ジャッジ時間 | 5,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 219 ms
44,132 KB |
testcase_07 | AC | 198 ms
44,204 KB |
testcase_08 | AC | 220 ms
44,076 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using graph=vector<vector<int>>; void add_edge(graph& G,int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } class union_find{ int n; vector<int> p; public: union_find(int n):n(n),p(n,-1){} int find(int u){ return p[u]<0?u:p[u]=find(p[u]); } void unite(int u,int v){ u=find(u); v=find(v); if(u!=v){ // 常に u を親にする // if(p[v]<p[u]) swap(u,v); p[u]+=p[v]; p[v]=u; n--; } } bool is_same(int u,int v){ return find(u)==find(v); } int size()const{ return n; } int size(int u){ return -p[find(u)]; } void make_set(){ n++; p.emplace_back(-1); } }; class Euler_tour_for_vertex{ vector<int> L,R; const graph& Tr; int idx; void dfs(int u,int p){ L[u]=idx++; for(int v:Tr[u]) if(v!=p) dfs(v,u); R[u]=idx; } public: Euler_tour_for_vertex(const graph& Tr,int root):L(Tr.size()),R(Tr.size()),Tr(Tr),idx(0){ dfs(root,-1); } int get_index(int u)const{ return L[u]; } pair<int,int> get_subtree(int u)const{ return {L[u],R[u]}; } }; template<class T> class segment_tree{ int n; vector<T> dat; void add(int l,int r,int a,int b,int u,T v){ if(l<=a && b<=r){ dat[u]+=v; return; } int c=(a+b+1)/2; if(l<c && a<r) add(l,r,a,c,2*u ,v); if(l<b && c<r) add(l,r,c,b,2*u+1,v); } public: segment_tree(int N){ for(n=1;n<N;n*=2); dat.assign(2*n,0); } void add(int l,int r,T v){ add(l,r,0,n,1,v); } T query(int u){ u+=n; T res=dat[u]; for(u/=2;u>=1;u/=2) res+=dat[u]; return res; } }; int main(){ int n,q; scanf("%d%d",&n,&q); int next=n; union_find U(n); graph T(n); vector<tuple<int,int,int>> Q; rep(i,q){ int type,a,b; scanf("%d%d%d",&type,&a,&b); if(type==1){ a--; b--; a=U.find(a); b=U.find(b); if(a!=b){ U.make_set(); U.unite(next,a); U.unite(next,b); T.emplace_back(); add_edge(T,a,next); add_edge(T,b,next); next++; } } else if(type==2){ a--; a=U.find(a); Q.emplace_back(type,a,b); } else{ a--; Q.emplace_back(type,a,b); } } int m=T.size(); Euler_tour_for_vertex ET(T,m-1); segment_tree<int> ST(m); rep(i,Q.size()){ int type,a,b; tie(type,a,b)=Q[i]; if(type==2){ int l,r; tie(l,r)=ET.get_subtree(a); ST.add(l,r,b); } else{ printf("%d\n",ST.query(ET.get_index(a))); } } return 0; }