結果
問題 | No.2536 同値性と充足可能性 |
ユーザー |
|
提出日時 | 2023-11-10 21:52:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 1,772 bytes |
コンパイル時間 | 1,988 ms |
コンパイル使用メモリ | 208,676 KB |
最終ジャッジ日時 | 2025-02-17 20:38:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; vector<vector<pair<int,int>>> Graph(N); for(int i=0; i<M; i++){ int u,v; string s; cin >> u >> s >> v; u--; v--; if(s == "<==>"){ Graph.at(u).push_back({v,0}); Graph.at(v).push_back({u,0}); } else{ Graph.at(u).push_back({v,1}); Graph.at(v).push_back({u,1}); } } vector<int> dist(N,-1); vector<int> answer; for(int i=0; i<N; i++){ if(dist.at(i) != -1) continue; int zero = 0,one = 0; vector<int> through; queue<int> Q; Q.push(i); dist.at(i) = 0; while(Q.size()){ int pos = Q.front(); Q.pop(); through.push_back(pos); int d = dist.at(pos); if(d == 0) zero++; else one++; for(auto [to,cost] : Graph.at(pos)){ int next = d^cost; if(dist.at(to) == -1){dist.at(to) = next; Q.push(to);} else if(dist.at(to) != next){cout << "No" << endl; return 0;} } } if(zero >= one){ for(auto v : through) if(dist.at(v) == 0) answer.push_back(v); } else{ for(auto v : through) if(dist.at(v) == 1) answer.push_back(v); } } sort(answer.begin(),answer.end()); if(answer.size() >= (N+1)/2){ cout << "Yes" << endl; cout << answer.size() << endl; for(int i=0; i<answer.size(); i++){ if(i) cout << " "; cout << answer.at(i)+1; } cout << endl; } else{cout << "No" << endl;} }