結果

問題 No.274 The Wall
ユーザー sf_kk
提出日時 2020-10-17 13:51:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 383 ms / 2,000 ms
コード長 3,998 bytes
コンパイル時間 1,233 ms
コンパイル使用メモリ 103,124 KB
実行使用メモリ 148,736 KB
最終ジャッジ日時 2025-03-17 19:08:12
合計ジャッジ時間 3,281 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <map>
#include <climits>
#include <bitset>
#include <ctime>

using ll = long long;
const ll INF = 1 << 29;

class TwoSAT
{
public:
    TwoSAT(const int literal_count)
            : V(literal_count), connection(2 * V), reversedConnection(2 * V), cmp(2 * V, -1){}

    void AddClosure(int x, int y)
    {
        AddEdge(x, y);

        // !x, !y が inout 似ない場合はこっち
        //  AddEdge((x + V) % (2 * V), y); // !x -> y
        //  AddEdge((y + V) % (2 * V), x); // !y -> x
    }

    std::pair<bool, std::vector<int>> Satisfy()
    {
        SCC();

        std::vector<int> ans(V);
        for(auto i = 0; i < V; i++)
        {
            // x -> !x 成り立つ = 同じグラフ上にあるとき充足不可能(矛盾)
            if(cmp[i] == cmp[V + i])
                return std::make_pair(false, ans);

            // そうでなければ充足可能な変数の組み合わせが存在する.
            // x が !x のトポロジカル順序より後なら x は真
            // ( dfs の探索順で先に判明した組み合わせの値を解として返す )
            ans[i] = (cmp[V + i] < cmp[i]);
        }

        return std::make_pair(true, ans);
    }

private:

    const int V;
    std::vector<std::vector<int>> connection, reversedConnection;
    std::vector<int> ps, cmp;

    void AddEdge(int from, int to)
    {
        connection[from].push_back(to);
        reversedConnection[to].push_back(from);
    }

    void DFS(int u)
    {
        cmp[u] = 0;
        for(auto v : connection[u])
        {
            if(cmp[v] == -1)
                DFS(v);
        }

        ps.push_back(u);
    }

    void RDFS(int u, int k)
    {
        cmp[u] = k;
        for(auto v : reversedConnection[u])
        {
            if(cmp[v] == -1)
                RDFS(v, k);
        }
    }

    void SCC()
    {
        for(auto i = 0; i < 2 * V; ++i)
        {
            if(cmp[i] == -1)
                DFS(i);
        }

        fill(cmp.begin(), cmp.end(), -1);

        int k = 0;
        for(auto i = 2 * V - 1; 0 <= i; --i)
        {
            if(cmp[ps[i]] == -1)
                RDFS(ps[i], k++);
        }
    }
};

int main()
{
    int N, M;
    std::cin >> N >> M;

    TwoSAT sat(N);
    std::vector<int> L(N);
    std::vector<int> R(N);
    std::vector<int> revL(N);
    std::vector<int> revR(N);

    for (auto i=0; i<N; ++i)
    {
        std::cin >> L[i] >> R[i];
        revR[i] = M - L[i] - 1;
        revL[i] = M - R[i] - 1;
    }

    for (auto i=0; i<N; i++)
    {
        for (auto j=0; j<i; j++)
        {
            // B が A に含まれてる -> どっちか回転 (B && !A) or (!B && A)
            if(L[i] <= R[j] && L[j] <= R[i])
            {
                sat.AddClosure(i, j + N);
                sat.AddClosure(i + N, j);
            }
            // 反転したB が A に含まれてる -> Bを回転しない or Aを回転 (!B && !A) or (B && A)
            if(L[i] <= revR[j] && revL[j] <= R[i])
            {
                sat.AddClosure(i, j);
                sat.AddClosure(i + N, j + i);
            }
            // B が 反転したA に含まれてる -> Bを回転 or Aを回転しない : (!A && !B) or (A && B)
            if(revL[i] <= R[j] && L[j] <= revR[i])
            {
                sat.AddClosure(j + N, i + N);
                sat.AddClosure(j, i);
            }
            // 反転したB が 反転したA に含まれてる -> どっちか回転 : (!A && B) or (A && !B)
            if(revL[i] <= revR[j] && revL[j] <= revR[i])
            {
                sat.AddClosure(j + N, i);
                sat.AddClosure(j, i + N);
            }
        }
    }

    auto result = sat.Satisfy();
    if (!result.first)
        std::cout << "NO" << std::endl;
    else
        std::cout << "YES" << std::endl;
}
0