結果
問題 | No.2294 Union Path Query (Easy) |
ユーザー |
|
提出日時 | 2023-05-05 22:13:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 385 ms / 4,000 ms |
コード長 | 1,237 bytes |
コンパイル時間 | 720 ms |
コンパイル使用メモリ | 73,600 KB |
実行使用メモリ | 57,008 KB |
最終ジャッジ日時 | 2024-11-23 08:12:56 |
合計ジャッジ時間 | 14,617 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<iostream> #include<vector> #include<cassert> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; int N,Q; struct dat{ vector<int>Vs; mint cnt[30]; }; int pr[2<<17]; dat V[2<<17]; int XOR[2<<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.push_back(i); for(int j=0;j<30;j++)V[i].cnt[j]=mint::raw(0); pr[i]=i; XOR[i]=0; } for(;Q--;) { int op;cin>>op; if(op==1) { int v,w;cin>>v>>w; { int pu=pr[X],pv=pr[v]; if(V[pu].Vs.size()<V[pv].Vs.size())swap(pu,pv); w^=XOR[v]^XOR[X]; for(int x:V[pv].Vs) { XOR[x]^=w; V[pu].Vs.push_back(x); pr[x]=pu; for(int j=0;j<30;j++)if(XOR[x]>>j&1)V[pu].cnt[j]++; } } } else if(op==2) { int u,v;cin>>u>>v; int pu=pr[u],pv=pr[v]; if(pu!=pv)cout<<"-1\n"; else { int d=XOR[u]^XOR[v]; cout<<d<<"\n"; X+=d; X%=N; } } else if(op==3) { int v;cin>>v; v=pr[v]; mint ans=0; for(int j=30;j--;) { mint c=V[v].cnt[j]; mint d=mint::raw(V[v].Vs.size())-c; ans=ans+ans+c*d; } cout<<ans.val()<<"\n"; } else { int v;cin>>v; X+=v; X%=N; } } }