結果

問題 No.2536 同値性と充足可能性
コンテスト
ユーザー ococonomy1
提出日時 2023-11-10 22:05:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 4,785 bytes
コンパイル時間 1,498 ms
コンパイル使用メモリ 119,636 KB
最終ジャッジ日時 2025-02-17 20:50:26
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
// #define AMARI 1000000007
#define TIME_LIMIT 1980000
#define el '\n'
#define El '\n'

// 重み付きUnionFind
class ococo_omomi_unionfind {
    class tri {
      public:
        int first;
        int second;
        ll omomi;
    };
    // できること
    // 点の挿入
    // その点の根を求める関数
    // 辺の挿入
    // 連結判定
    // 島が何個あるかの出力
  public:
    int simakosuu = 0;

    ococo_omomi_unionfind(int n = 0) {
        for(int i = 0; i < n; i++) vinsert();
    }
    vector<tri> g;
    // 点の挿入 O(1)
    // デフォルトの重みは0
    void vinsert(void) {
        tri temp;
        temp.first = g.size();
        temp.second = 1;
        temp.omomi = 0;
        g.push_back(temp);
        simakosuu++;
    }
    // ある点の根を求める関数 O(a(N))
    int ne(int a) {
        if(g[a].first == a) return a;
        else {
            int r = ne(g[a].first);
            g[a].omomi += g[g[a].first].omomi;
            return g[a].first = r;
        }
    }
    // 辺の挿入 O(a(N))
    // a(a1)からb(a2)に行く時、コストがwかかる
    // aとbが既に繋がっている場合、特に何もせずfalseを返す
    bool einsert(int a, int b, ll w) {
        if(a != b) {
            int a1 = ne(a), a2 = ne(b);
            if(a1 != a2) {
                simakosuu--;
                // a2の方がrankが大きいのでa1の上をa2にする
                if(g[a1].second < g[a2].second) {
                    g[a1].first = a2;
                    g[a2].second = max(g[a1].second + 1, g[a2].second);
                    g[a1].omomi -= g[a].omomi;
                    g[a1].omomi += g[b].omomi;
                    g[a1].omomi += w;
                } else {
                    g[a2].first = a1;
                    g[a1].second = max(g[a2].second + 1, g[a1].second);
                    g[a2].omomi -= g[b].omomi;
                    g[a2].omomi += g[a].omomi;
                    g[a2].omomi -= w;
                }
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    // 2つのノードの重みの差を返す関数
    // 2つのノードが繋がっていない場合LLONG_MINを返す
    // 2つのノードが連結である時、aからbに行くのにかかるコストを返す
    ll renketucheck(int a, int b) {
        if(ne(a) == ne(b)) {
            return g[b].omomi - g[a].omomi;
        } else return LLONG_MIN;
    }
    // 何個の島に分かれているか出力する関数 O(1)
    int islandnum(void) {
        return simakosuu;
    }
};

#define MULTI_TEST_CASE false
void solve(void) {
    int n,m;
    cin >> n >> m;
    ococo_omomi_unionfind uf(n);
    bool dame = false;
    for(int i = 0; i < m; i++){
        int u,v;
        string s;
        cin >> u >> s >> v;
        u--; v--;
        int dif = 1;
        if(s.size() == 4)dif--;
        if(uf.renketucheck(u,v) != LLONG_MIN && abs(uf.renketucheck(u,v)) % 2 == (1 - dif)){
            dame = true;
        }
        else uf.einsert(u,v,dif);
    }
    if(dame){
        cout << "No" << el;
        return;
    }
    vector<vector<int>> zero(n),one(n);
    for(int i = 0; i < n; i++){
        if(uf.renketucheck(i,uf.ne(i)) % 2 == 0)zero[uf.ne(i)].push_back(i);
        else one[uf.ne(i)].push_back(i);
    }
    
    vector<int> ans;
    for(int i = 0; i < n; i++){
        if(one[i].empty() && zero[i].empty())continue;
        if(zero[i].size() > one[i].size()){
            for(int j = 0; j < zero[i].size(); j++){
                ans.push_back(zero[i][j]);
            }
        }
        else{
            for(int j = 0; j < one[i].size(); j++){
                ans.push_back(one[i][j]);
            }
        }
    }
    cout << "Yes" << el;
    sort(ans.begin(),ans.end());
    cout << ans.size() << el;
    for(int i = 0; i < ans.size(); i++){
        if(i)cout << ' ';
        cout << ans[i] + 1;
    }
    cout << el;
    return;
}

void calc(void) {
    return;
}

signed main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE) cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}
0