結果

問題 No.274 The Wall
ユーザー Jikky1618
提出日時 2025-08-13 21:42:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 4,037 bytes
コンパイル時間 3,957 ms
コンパイル使用メモリ 296,372 KB
実行使用メモリ 132,224 KB
最終ジャッジ日時 2025-08-13 21:42:21
合計ジャッジ時間 6,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

struct StrongConnectedComponents {
    int N;
    vector<int> order, comp;
    vector<vector<int>> G_rev, groups, dag;
    StrongConnectedComponents(const vector<vector<int>>& G) : N(G.size()) {
        // 辺が逆向きのグラフ G_rev を構築
        G_rev.resize(N);
        for (int u = 0; u < N; u++) {
            for (auto&& v : G[u]) {
                G_rev[v].emplace_back(u);
            }
        }
        comp.resize(N, -2);
        // comp[i] = -2: 未訪問, -1: dfs で訪問済, id: dfs2 で訪問済
        for (int i = 0; i < N; i++) {
            if (comp[i] != -2) continue;
            dfs(G, i);
        }
        int id = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (comp[order[i]] != -1) continue;
            dfs2(order[i], id), id++;
        }
        G_rev.clear(), order.clear();
        groups.resize(id), dag.resize(id);
        for (int i = 0; i < N; i++) {
            groups[comp[i]].emplace_back(i);
            for (auto&& to : G[i]) {
                if (comp[i] == comp[to]) continue;
                dag[comp[i]].emplace_back(comp[to]);
            }
        }
    }
    void dfs(const vector<vector<int>>& G, int pos) {
        comp[pos] = -1;
        for (auto&& to : G[pos]) {
            if (comp[to] != -2) continue;
            dfs(G, to);
        }
        order.emplace_back(pos);
    }
    void dfs2(int pos, int id) {
        comp[pos] = id;
        for (auto&& to : G_rev[pos]) {
            if (comp[to] != -1) continue;
            dfs2(to, id);
        }
    }
};

struct twosat {
    int n;
    vector<bool> ans;
    vector<vector<int>> G;
    twosat(int n0) : n(n0), G(2 * n0) {}

    // 論理変数を追加する
    int add_var() {
        G.emplace_back(2);
        return n++;
    }

    // (not i) は ~i で表現
    void add_clause(int i, int j) {
        i = (i < 0 ? ~i : i) * 2 + (i < 0 ? 0 : 1);
        j = (j < 0 ? ~j : j) * 2 + (j < 0 ? 0 : 1);
        G[i ^ 1].emplace_back(j);
        G[j ^ 1].emplace_back(i);
    }
    void add_implication(int i, int j) { add_clause(~i, j); }
    void set_val(int i) { add_clause(i, i); }
    void at_most_one(const vector<int>& nodes) {
        int L = ssize(nodes);
        if (L <= 1) return;
        int cur = add_var(), nxt;
        for (int i = 0; i < L; i++) {
            add_clause(~nodes[i], cur);
            if (i + 1 < L) {
                nxt = add_var();
                add_clause(~cur, nxt);
                add_clause(~cur, ~nodes[i + 1]);
            }
            swap(cur, nxt);
        }
    }

    bool satisfiable() {
        ans.clear();
        StrongConnectedComponents scc(G);
        for (int i = 0; i < n; i++) {
            if (scc.comp[2 * i] == scc.comp[2 * i + 1]) return false;
        }
        ans.resize(n);
        for (int i = 0; i < n; i++) {
            ans[i] = (scc.comp[2 * i] < scc.comp[2 * i + 1]);
        }
        return true;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N, M;
    cin >> N >> M;
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++) cin >> L[i] >> R[i];

    // 論理変数: x[i] := 反転したかどうか
    twosat ts(N);
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (max(L[i], L[j]) <= min(R[i], R[j])) {
                // not(not(i) and not(j)) = i or j
                ts.add_clause(i, j);
            }
            if (max(L[i], M - R[j] - 1) <= min(R[i], M - L[j] - 1)) {
                ts.add_clause(i, ~j);
            }
            if (max(M - R[i] - 1, L[j]) <= min(M - L[i] - 1, R[j])) {
                ts.add_clause(~i, j);
            }
            if (max(M - R[i] - 1, M - R[j] - 1) <= min(M - L[i] - 1, M - L[j] - 1)) {
                ts.add_clause(~i, ~j);
            }
        }
    }
    cout << (ts.satisfiable() ? "YES" : "NO") << '\n';
}
0