結果
問題 | No.2295 Union Path Query (Medium) |
ユーザー | 沙耶花 |
提出日時 | 2023-05-05 22:57:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,355 ms / 4,000 ms |
コード長 | 4,446 bytes |
コンパイル時間 | 5,654 ms |
コンパイル使用メモリ | 270,440 KB |
実行使用メモリ | 111,476 KB |
最終ジャッジ日時 | 2023-10-09 22:00:29 |
合計ジャッジ時間 | 103,503 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2,590 ms
34,380 KB |
testcase_04 | AC | 2,399 ms
59,784 KB |
testcase_05 | AC | 1,709 ms
59,484 KB |
testcase_06 | AC | 1,154 ms
109,948 KB |
testcase_07 | AC | 2,179 ms
34,288 KB |
testcase_08 | AC | 1,355 ms
109,840 KB |
testcase_09 | AC | 1,335 ms
109,936 KB |
testcase_10 | AC | 1,556 ms
109,880 KB |
testcase_11 | AC | 2,630 ms
109,788 KB |
testcase_12 | AC | 3,355 ms
109,784 KB |
testcase_13 | AC | 2,186 ms
34,840 KB |
testcase_14 | AC | 640 ms
16,772 KB |
testcase_15 | AC | 516 ms
109,640 KB |
testcase_16 | AC | 481 ms
109,756 KB |
testcase_17 | AC | 752 ms
61,328 KB |
testcase_18 | AC | 1,730 ms
59,796 KB |
testcase_19 | AC | 2,070 ms
59,988 KB |
testcase_20 | AC | 1,168 ms
60,108 KB |
testcase_21 | AC | 1,140 ms
59,972 KB |
testcase_22 | AC | 1,927 ms
60,048 KB |
testcase_23 | AC | 1,903 ms
110,780 KB |
testcase_24 | AC | 1,812 ms
110,200 KB |
testcase_25 | AC | 698 ms
110,868 KB |
testcase_26 | AC | 1,688 ms
110,340 KB |
testcase_27 | AC | 1,617 ms
110,964 KB |
testcase_28 | AC | 1,598 ms
110,548 KB |
testcase_29 | AC | 1,506 ms
110,176 KB |
testcase_30 | AC | 1,528 ms
111,096 KB |
testcase_31 | AC | 1,491 ms
110,952 KB |
testcase_32 | AC | 1,464 ms
110,964 KB |
testcase_33 | AC | 1,455 ms
111,476 KB |
testcase_34 | AC | 1,468 ms
109,956 KB |
testcase_35 | AC | 1,443 ms
110,080 KB |
testcase_36 | AC | 1,462 ms
110,728 KB |
testcase_37 | AC | 1,440 ms
110,008 KB |
testcase_38 | AC | 1,462 ms
110,588 KB |
testcase_39 | AC | 1,455 ms
110,752 KB |
testcase_40 | AC | 1,449 ms
110,916 KB |
testcase_41 | AC | 1,468 ms
111,140 KB |
testcase_42 | AC | 1,424 ms
110,232 KB |
testcase_43 | AC | 1,422 ms
110,716 KB |
testcase_44 | AC | 2,195 ms
111,008 KB |
testcase_45 | AC | 1,823 ms
110,964 KB |
testcase_46 | AC | 1,390 ms
110,740 KB |
testcase_47 | AC | 1,535 ms
110,004 KB |
testcase_48 | AC | 2,265 ms
110,716 KB |
testcase_49 | AC | 2,348 ms
110,588 KB |
testcase_50 | AC | 1,152 ms
110,200 KB |
testcase_51 | AC | 1,442 ms
110,824 KB |
testcase_52 | AC | 1,551 ms
110,964 KB |
testcase_53 | AC | 1,454 ms
110,692 KB |
testcase_54 | AC | 1,490 ms
110,688 KB |
testcase_55 | AC | 1,496 ms
110,016 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 template <typename T> struct perArray{ struct node{ T value; int l=-1,r=-1; }; int sz; vector<node> nodes; vector<int> roots; void build(vector<T> v,int now = -1){ if(now==-1){ sz = v.size(); nodes.push_back(node()); now = 0; roots.push_back(0); } if(v.size()==1){ nodes[now].value = v[0]; return; } vector<T> l,r; rep(i,v.size()){ if(i<v.size()/2){ l.push_back(v[i]); } else{ r.push_back(v[i]); } } nodes[now].l = nodes.size(); nodes.push_back(node()); build(l,nodes[now].l); nodes[now].r = nodes.size(); nodes.push_back(node()); build(r,nodes[now].r); } int set(int p, int ind, T x, int now = -1, int length = -1){ int ret = roots.size(); if(now==-1){ roots.push_back(nodes.size()); now = nodes.size(); nodes.push_back(nodes[roots[p]]); length = sz; } if(length==1){ nodes[now].value = x; } else{ if(ind < (length>>1)){ int temp = nodes[now].l; nodes[now].l = nodes.size(); nodes.push_back(nodes[temp]); set(p,ind,x,nodes.size()-1,(length>>1)); } else{ int temp = nodes[now].r; nodes[now].r = nodes.size(); nodes.push_back(nodes[temp]); set(p,ind - (length>>1),x,nodes.size()-1,(length+1)>>1); } } return ret; } T get(int p,int ind,int now = -1,int length = -1){ if(now==-1){ now = roots[p]; length = sz; } if(length==1)return nodes[now].value; if(ind<(length>>1)){ return get(p,ind,nodes[now].l,length>>1); } else{ return get(p,ind - (length>>1),nodes[now].r,(length+1)>>1); } } int size(){ return sz; } }; struct perDsu{ perArray<int> A; vector<int> roots; perDsu(int n){ vector<int> t(n,-1); A.build(t); roots.push_back(0); } int merge(int p,int a,int b){ int ret = roots.size(); int La = leader(p,a); int Lb = leader(p,b); if(La==Lb)return p; if(size(p,La)<size(p,Lb))swap(La,Lb); int temp = A.set(roots[p],La,-(size(p,La)+size(p,Lb))); roots.push_back(A.set(temp,Lb,La)); return ret; } bool same(int p,int a,int b){ return (leader(p,a)==leader(p,b)); } int size(int p,int a){ int temp = A.get(roots[p],a); if(temp<0)return -temp; return size(p,temp); } int leader(int p,int a){ int temp = A.get(roots[p],a); if(temp<0)return a; return leader(p,temp); } vector<vector<int>> groups(int p){ vector<vector<int>> temp(A.size(),vector<int>()); rep(i,A.size()){ temp[leader(p,i)].push_back(i); } vector<vector<int>> ret; rep(i,temp.size()){ if(temp[i].size()>0)ret.push_back(temp[i]); } return ret; } }; int main(){ int n,x0,q; cin>>n>>x0>>q; perDsu D(n); vector<int> t(q+1),a(q+1),b(q+1),p(q+1); int x= x0; vector<int> memo(q+1,-1); vector<int> is(1,0); for(int i=1;i<=q;i++){ scanf("%d",&t[i]); p[i] = p[i-1]; if(t[i]==1){ scanf("%d %d",&a[i],&b[i]); //cin>>a[i]>>b[i]; p[i] = D.merge(p[i],a[i],x); is.push_back(i); } if(t[i]==2){ scanf("%d %d",&a[i],&b[i]); if(a[i]==b[i])continue; if(D.same(p[i],a[i],b[i])){ int ok = 0,ng = is.size(); while(ng-ok>1){ int mid = (ok+ng)/2; if(D.same(p[is[mid]],a[i],b[i]))ng = mid; else ok = mid; } memo[i] = b[is[ok+1]]; x += memo[i]; x %= n; } } if(t[i]==3){ scanf("%d",&a[i]); } if(t[i]==4){ scanf("%d",&a[i]); x += a[i]; x %= n; } } //cout<<'a'<<endl; x = x0; dsu D2(n); vector<mint> A(n); for(int i=1;i<=q;i++){ if(t[i]==1){ int la = D2.leader(a[i]),lb = D2.leader(x); if(D2.same(la,lb))continue; mint tt = D2.size(a[i]); tt *= D2.size(x); tt *= b[i]; tt += A[la] + A[lb]; D2.merge(la,lb); int lc = D2.leader(la); int ld = lc^la^lb; A[ld] = 0; A[lc] = tt; } if(t[i]==2){ if(a[i]==b[i]){ printf("0\n"); continue; } printf("%d\n",memo[i]); if(memo[i]!=-1){ x += memo[i]; x %= n; } /* if(D.same(p[i],a[i],b[i])){ x += memo[i]; x %= n; printf("%d\n",memo[i]); //cout<<b[ok+1]<<endl; } else printf("-1\n"); */ } if(t[i]==3){ printf("%d\n",A[D2.leader(a[i])].val()); } if(t[i]==4){ x += a[i]; x %= n; } } return 0; }