結果

問題 No.274 The Wall
ユーザー ks115ks115
提出日時 2021-08-12 18:02:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 3,519 bytes
コンパイル時間 2,740 ms
コンパイル使用メモリ 216,416 KB
実行使用メモリ 132,736 KB
最終ジャッジ日時 2024-10-01 22:35:03
合計ジャッジ時間 4,886 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 173 ms
70,144 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 481 ms
132,736 KB
testcase_12 AC 18 ms
6,816 KB
testcase_13 AC 2 ms
6,816 KB
testcase_14 AC 5 ms
6,820 KB
testcase_15 AC 10 ms
6,820 KB
testcase_16 AC 72 ms
28,672 KB
testcase_17 AC 71 ms
28,288 KB
testcase_18 AC 73 ms
29,440 KB
testcase_19 AC 15 ms
6,816 KB
testcase_20 AC 18 ms
6,820 KB
testcase_21 AC 18 ms
6,816 KB
testcase_22 AC 19 ms
6,816 KB
testcase_23 AC 19 ms
6,816 KB
testcase_24 AC 19 ms
6,820 KB
testcase_25 AC 18 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

class StronglyConnectedComponents {
   public:
    StronglyConnectedComponents(vector<vector<int>> &G) {
        vector<int> postorder;
        vector<bool> visited(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            if (visited[i]) continue;
            dfs(G, visited, postorder, i);
        }

        rg.resize(G.size());
        for (int i = 0; i < (int)G.size(); i++) {
            for (auto g : G[i]) rg[g].push_back(i);
        }

        c = 0;
        _id.resize(G.size(), 0);
        for (int i = (int)G.size() - 1; i >= 0; i--) {
            if (_id[postorder[i]]) continue;
            vector<int> components;
            rdfs(rg, components, postorder[i], ++c);
            scc.push_back(components);
        }
    }

    int size() {
        return c;
    }

    int id(int u) {
        return _id[u];
    }

    bool same(int u, int v) {
        return _id[u] == _id[v];
    }

    vector<vector<int>> reverseGraph() {
        return rg;
    }

    vector<vector<int>> getComponents() {
        return scc;
    }
   
   private:
    int c;
    vector<int> _id;
    vector<vector<int>> rg, scc;

    void dfs(vector<vector<int>> &G, vector<bool> &visited, vector<int> &postorder, int v) {
        visited[v] = true;
        for (auto g : G[v]) {
            if (visited[g]) continue;
            dfs(G, visited, postorder, g);
        }
        postorder.push_back(v);
    }

    void rdfs(vector<vector<int>> &G, vector<int> &components, int v, int c) {
        _id[v] = c; components.push_back(v);
        for (auto g : G[v]) {
            if (_id[g]) continue;
            rdfs(G, components, g, c);
        }
    }
};

class TwoSat {
   private:
    const int sz;
    vector<int> b;
    vector<vector<int>> G;
    StronglyConnectedComponents *scc;

   public:
    TwoSat(int n) : sz(n), b(sz), G(2 * sz) {}

    void addEdge(int u, bool notu, int v, bool notv) {
        int u0 = notu ? u + sz : u;
        int u1 = notu ? u : u + sz;
        int v0 = notv ? v + sz : v;
        int v1 = notv ? v : v + sz;
        G[u1].push_back(v0);
        G[v1].push_back(u0);
    }

    bool isSatisfiable() {
        scc = new StronglyConnectedComponents(G);
        for (int i = 0; i < sz; i++) {
            if (scc->same(i, i + sz)) return false;
        } 
        return true;
    }

    vector<int> & assign() {
        for (int i = 0; i < sz; i++) {
            b[i] = scc->id(i) > scc->id(i + sz);
        }
        return b;
    }

};

int main() {
    int N, M; cin >> N >> M;
    vector<int> L(N), R(N);
    REP(i, 0, N) cin >> L[i] >> R[i];

    auto rev = [&](int x) -> int {
        return M - x - 1;
    };

    TwoSat ts(N);
    REP(i, 0, N) {
        REP(j, i + 1, N) {
            if (max(L[i], L[j]) <= min(R[i], R[j])) {
                ts.addEdge(i, true, j, true);
            }
            if (max(rev(R[i]), L[j]) <= min(rev(L[i]), R[j])) {
                ts.addEdge(i, false, j, true);
            }
            if (max(L[i], rev(R[j])) <= min(R[i], rev(L[j]))) {
                ts.addEdge(i, true, j, false);
            }
            if (max(rev(R[i]), rev(R[j])) <= min(rev(L[i]), rev(L[j]))) {
                ts.addEdge(i, false, j, false);
            }
        }
    }

    if (ts.isSatisfiable()) cout << "YES" << endl;
    else cout << "NO" << endl;
    
    return 0;
}
0