結果
問題 | No.2536 同値性と充足可能性 |
ユーザー |
![]() |
提出日時 | 2023-09-18 14:44:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 1,727 bytes |
コンパイル時間 | 8,052 ms |
コンパイル使用メモリ | 352,344 KB |
実行使用メモリ | 14,544 KB |
最終ジャッジ日時 | 2024-07-05 05:31:24 |
合計ジャッジ時間 | 10,550 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#ifndef DEBUG #pragma GCC target("avx2") #pragma GCC optimize("Ofast,unroll-loops") #endif #include <bits/stdc++.h> #include <atcoder/all> #define rep(i, n) for (int i = 0; i < n; i++) #define ALL(a) a.begin(), a.end() #define ll long long using namespace std; using namespace atcoder; void solve() { int n, m; cin >> n >> m; dsu d(2 * n); vector<vector<int>> g(2 * n); rep(qqq, m) { int i, j; string s; cin >> i >> s >> j; i--, j--; if (s.length() == 4) { d.merge(i, j); d.merge(i + n, j + n); g[i].push_back(j); g[j].push_back(i); g[i + n].push_back(j + n); g[j + n].push_back(i + n); } else { d.merge(i, j + n); d.merge(i + n, j); g[i].push_back(j + n); g[j + n].push_back(i); g[j].push_back(i + n); g[i + n].push_back(j); } } rep(i, n) { if (d.same(i, i + n)) { cout << "No" << '\n'; return; } } vector<int> ans; vector<bool> used(n); queue<int> q; rep(st, n) { if (used[st]) continue; vector<int> ans1, ans2; ans1.push_back(st); used[st] = true; q.push(st); while (!q.empty()) { const int x = q.front(); q.pop(); for (int i : g[x]) { if (used[i % n]) continue; if (i < n) ans1.push_back(i); else ans2.push_back(i - n); used[i % n] = true; q.push(i); } } if (ans1.size() > ans2.size())for (int i : ans1) ans.push_back(i); else for (int i : ans2) ans.push_back(i); } if (ans.size() * 2 < n) { cout << "No" << '\n'; return; } sort(ALL(ans)); int size = ans.size(); cout << "Yes" << '\n'; cout << size << '\n'; rep(i, size) cout << ans[i] + 1 << " \n"[i + 1 == size]; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(40); solve(); return 0; }