結果
問題 | No.2295 Union Path Query (Medium) |
ユーザー |
|
提出日時 | 2023-05-05 22:33:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 563 ms / 4,000 ms |
コード長 | 1,914 bytes |
コンパイル時間 | 810 ms |
コンパイル使用メモリ | 83,832 KB |
実行使用メモリ | 100,156 KB |
最終ジャッジ日時 | 2024-11-23 09:37:03 |
合計ジャッジ時間 | 26,160 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include<iostream>#include<vector>#include<set>#include<cassert>#include<atcoder/modint>using namespace std;using mint=atcoder::modint998244353;int N,Q;struct dat{set<int>Vs;vector<pair<int,int> >Qs;mint ans;};int pr[2<<17];dat V[2<<17];int ans[3<<17];int op[3<<17],A[3<<17],B[3<<17];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,X,Q;cin>>N>>X>>Q;for(int i=0;i<N;i++){V[i].Vs.insert(i);V[i].Qs.clear();V[i].ans=mint::raw(0);pr[i]=i;}for(int i=0;i<Q;i++){cin>>op[i];if(op[i]==1){cin>>A[i]>>B[i];}else if(op[i]==2){cin>>A[i]>>B[i];if(A[i]==B[i])ans[i]=0;else{V[A[i]].Qs.push_back(make_pair(B[i],i));V[B[i]].Qs.push_back(make_pair(A[i],i));ans[i]=2e9;}}else if(op[i]==3){cin>>A[i];}else{cin>>A[i];}}for(int i=0;i<Q;i++){if(op[i]==1){int v=A[i],w=B[i];int pu=pr[X],pv=pr[v];if(pu==pv)continue;if(V[pu].Vs.size()<V[pv].Vs.size())swap(pu,pv);V[pu].ans+=mint(w)*V[pu].Vs.size()*V[pv].Vs.size();V[pu].ans+=V[pv].ans;if(V[pu].Qs.size()>V[pv].Qs.size()){for(pair<int,int>q:V[pv].Qs){int x=q.first;if(V[pu].Vs.find(x)!=V[pu].Vs.end()){ans[q.second]=min(ans[q.second],w);}else V[pu].Qs.push_back(q);}}else{for(pair<int,int>q:V[pu].Qs){int x=q.first;if(V[pv].Vs.find(x)!=V[pv].Vs.end()){ans[q.second]=min(ans[q.second],w);}else V[pv].Qs.push_back(q);}swap(V[pu].Qs,V[pv].Qs);}for(int x:V[pv].Vs){V[pu].Vs.insert(x);pr[x]=pu;}}else if(op[i]==2){int d=ans[i];if(d==(int)2e9)cout<<"-1\n";else{cout<<d<<"\n";X+=d;X%=N;}}else if(op[i]==3){int v=pr[A[i]];cout<<V[v].ans.val()<<"\n";}else{X+=A[i];X%=N;}}}