結果

問題 No.274 The Wall
ユーザー sf_kksf_kk
提出日時 2020-10-17 13:51:24
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 415 ms / 2,000 ms
コード長 3,998 bytes
コンパイル時間 1,113 ms
コンパイル使用メモリ 103,344 KB
実行使用メモリ 148,908 KB
最終ジャッジ日時 2023-09-28 07:42:46
合計ジャッジ時間 3,693 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 135 ms
69,232 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 415 ms
148,908 KB
testcase_12 AC 9 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 5 ms
4,380 KB
testcase_15 AC 10 ms
4,376 KB
testcase_16 AC 104 ms
38,604 KB
testcase_17 AC 95 ms
37,040 KB
testcase_18 AC 100 ms
39,888 KB
testcase_19 AC 16 ms
4,380 KB
testcase_20 AC 18 ms
4,376 KB
testcase_21 AC 19 ms
4,376 KB
testcase_22 AC 20 ms
4,376 KB
testcase_23 AC 20 ms
4,376 KB
testcase_24 AC 21 ms
4,380 KB
testcase_25 AC 20 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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