結果
問題 | No.2293 無向辺 2-SAT |
ユーザー |
|
提出日時 | 2023-05-05 21:54:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 4,000 ms |
コード長 | 1,103 bytes |
コンパイル時間 | 745 ms |
コンパイル使用メモリ | 72,576 KB |
実行使用メモリ | 8,968 KB |
最終ジャッジ日時 | 2024-11-23 07:14:50 |
合計ジャッジ時間 | 11,497 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include<iostream>#include<vector>#include<atcoder/modint>using namespace std;using mint=atcoder::modint998244353;int N,Q;int pr[4<<17];vector<int>hist;int find(int u){if(pr[u]>=0)return pr[u]=find(pr[u]);else return u;}bool merge(int u,int v){u=find(u);v=find(v);if(u==v)return false;if(-pr[u]<-pr[v])swap(u,v);pr[u]+=pr[v];pr[v]=u;hist.push_back(u);hist.push_back(v);return true;}void clear(){for(int u:hist)pr[u]=-1;hist.clear();}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>Q;for(int i=0;i<N+N;i++)pr[i]=-1;int cnt=2*N;const mint inv2=mint::raw(2).inv();const mint all=mint::raw(2).pow(N);mint now=all;for(;Q--;){int op;cin>>op;if(op==1){int u,v;cin>>u>>v;u--,v--;if(merge(u,v)){if(merge(u+N,v+N))now*=inv2;else{now=mint::raw(0);}}}else if(op==2){int u,v;cin>>u>>v;u--,v--;if(merge(u,v+N)){if(merge(u+N,v))now*=inv2;else{now=mint::raw(0);}}}else{clear();now=all;}cout<<now.val()<<"\n";}}