結果

問題 No.2536 同値性と充足可能性
ユーザー AerenAeren
提出日時 2023-11-10 21:55:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,731 bytes
コンパイル時間 3,538 ms
コンパイル使用メモリ 265,652 KB
実行使用メモリ 13,496 KB
最終ジャッジ日時 2024-09-26 01:27:06
合計ジャッジ時間 8,259 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 8 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 i = 0; i < (int)res.size(); ++ i){
cout << res[i] + 1 << " "[i == (int)res.size() - 1];
}
cout << "\n";
}
else{
cout << "No\n";
}
return 0;
}
/*
*/
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by Aeren //
// //
////////////////////////////////////////////////////////////////////////////////////////
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0