結果

問題 No.2536 同値性と充足可能性
ユーザー ococonomy1ococonomy1
提出日時 2023-11-10 21:50:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,671 bytes
コンパイル時間 1,500 ms
コンパイル使用メモリ 123,192 KB
実行使用メモリ 12,056 KB
最終ジャッジ日時 2024-09-26 01:24:06
合計ジャッジ時間 5,697 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,940 KB
testcase_02 WA -
testcase_03 AC 2 ms
6,944 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 3 ms
6,940 KB
testcase_24 AC 3 ms
6,944 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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);
    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)){
            cout << "No" << el;
            return;
        }
        uf.einsert(u,v,dif);
    }
    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]);
            }
        }
    }
    sort(ans.begin(),ans.end());
    cout << ans.size() << el;
    for(int i = 0; i < ans.size(); i++){
        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