結果
問題 | No.2536 同値性と充足可能性 |
ユーザー |
|
提出日時 | 2023-11-10 21:49:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,674 bytes |
コンパイル時間 | 3,209 ms |
コンパイル使用メモリ | 265,508 KB |
実行使用メモリ | 13,284 KB |
最終ジャッジ日時 | 2024-09-26 01:23:26 |
合計ジャッジ時間 | 7,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 23 |
ソースコード
#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;using namespace numbers;template<bool Enable_small_to_large = true>struct disjoint_set{int n, _classes;vector<int> p;disjoint_set(int n): n(n), _classes(n), p(n, -1){ }int make_set(){p.push_back(-1);++ _classes;return n ++;}int classes() const{return _classes;}int root(int u){return p[u] < 0 ? u : p[u] = root(p[u]);}bool share(int a, int b){return root(a) == root(b);}int size(int u){return -p[root(u)];}bool merge(int u, int v){u = root(u), v = root(v);if(u == v) return false;-- _classes;if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);p[u] += p[v], p[v] = u;return true;}bool merge(int u, int v, auto act){u = root(u), v = root(v);if(u == v) return false;-- _classes;bool swapped = false;if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;p[u] += p[v], p[v] = u;act(u, v, swapped);return true;}void clear(){_classes = n;fill(p.begin(), p.end(), -1);}vector<vector<int>> group_up(){vector<vector<int>> g(n);for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());return g;}};int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int n, m;cin >> n >> m;disjoint_set dsu(n << 1);for(auto i = 0; i < m; ++ i){int u, v;string type;cin >> u >> type >> v, -- u, -- v;for(auto t = 0; t < 2; ++ t){dsu.merge(u << 1 | t, v << 1 | t ^ (type == string("<=/=>")));}}vector<int> res, vis(n);for(auto g: dsu.group_up()){if(vis[g[0] >> 1]){continue;}for(auto u2: g){vis[u2 >> 1] = true;}if(dsu.share(g[0], g[0] ^ 1)){continue;}array<int, 2> cnt{};for(auto u2: g){++ cnt[u2 & 1];}int rem = cnt[0] < cnt[1];for(auto u2: g){if(u2 % 2 == rem){res.push_back(u2 >> 1);}}}if((int)res.size() * 2 >= n){ranges::sort(res);cout << "Yes\n" << (int)res.size() << "\n";for(auto u: res){cout << u + 1 << " ";}cout << "\n";}else{cout << "No\n";}return 0;}/**/////////////////////////////////////////////////////////////////////////////////////////// //// Coded by Aeren //// //////////////////////////////////////////////////////////////////////////////////////////