結果
問題 | No.2536 同値性と充足可能性 |
ユーザー | Aeren |
提出日時 | 2023-11-10 22:05:40 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,733 bytes |
コンパイル時間 | 3,323 ms |
コンパイル使用メモリ | 259,964 KB |
実行使用メモリ | 13,308 KB |
最終ジャッジ日時 | 2024-09-26 01:36:20 |
合計ジャッジ時間 | 5,447 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 4 ms
5,376 KB |
testcase_21 | AC | 4 ms
5,376 KB |
testcase_22 | AC | 4 ms
5,376 KB |
testcase_23 | AC | 24 ms
5,376 KB |
testcase_24 | AC | 25 ms
5,376 KB |
testcase_25 | AC | 54 ms
12,672 KB |
testcase_26 | AC | 53 ms
13,184 KB |
testcase_27 | AC | 54 ms
12,544 KB |
testcase_28 | AC | 51 ms
13,056 KB |
testcase_29 | AC | 53 ms
13,184 KB |
testcase_30 | AC | 54 ms
13,308 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; 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)){ cout << "No\n"; return 0; } 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){ sort(res.begin(), res.end()); cout << "Yes\n" << (int)res.size() << "\n"; for(auto i = 0; i < (int)res.size(); ++ i){ cout << res[i] + 1; if(i < (int)res.size() - 1){ cout << " "; } } cout << "\n"; } else{ cout << "No\n"; } return 0; } /* */ //////////////////////////////////////////////////////////////////////////////////////// // // // Coded by Aeren // // // ////////////////////////////////////////////////////////////////////////////////////////