結果

問題 No.274 The Wall
ユーザー ninjaninja
提出日時 2019-07-05 10:41:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 669 ms / 2,000 ms
コード長 3,114 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 187,184 KB
実行使用メモリ 382,732 KB
最終ジャッジ日時 2023-09-04 02:40:26
合計ジャッジ時間 4,918 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 243 ms
151,964 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 669 ms
382,732 KB
testcase_12 AC 15 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 8 ms
4,376 KB
testcase_15 AC 16 ms
4,380 KB
testcase_16 AC 172 ms
87,016 KB
testcase_17 AC 165 ms
83,356 KB
testcase_18 AC 175 ms
90,172 KB
testcase_19 AC 30 ms
4,380 KB
testcase_20 AC 35 ms
4,388 KB
testcase_21 AC 37 ms
4,384 KB
testcase_22 AC 39 ms
4,700 KB
testcase_23 AC 38 ms
4,400 KB
testcase_24 AC 38 ms
4,560 KB
testcase_25 AC 38 ms
4,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

class G {
public:
  vector<vector<int>> p, inv, sp, sinv;
  int n, m;
  vector<int> b, c, depth;
  vector<bool> a;

  G(int nn, vector<vector<int>> &np, vector<vector<int>> &ninv) {
    n = nn;
    p = np;
    inv = ninv;
    a.resize(n);
    c.resize(n);
    for (int i = 0; i < n; i++) {
      c[i] = -1;
    }
  }

  void dfs(int i) {
    if (a[i])
      return;
    a[i] = true;
    for (int j = 0; j < p[i].size(); j++) {
      if (a[p[i][j]]) {
        continue;
      }
      dfs(p[i][j]);
    }
    b.push_back(i);
  }

  void dfs2(int i, int id) {
    if (c[i] > -1)
      return;
    c[i] = id;
    for (int j = 0; j < inv[i].size(); j++) {
      if (c[inv[i][j]] > -1)
        continue;
      dfs2(inv[i][j], id);
    }
  }

  void solve() {
    for (int i = 0; i < n; i++) {
      dfs(i);
    }
    int j = 0;
    for (int i = n - 1; i >= 0; i--) {
      if (c[b[i]] > -1)
        continue;
      dfs2(b[i], j++);
    }
    m = j;
    sp.resize(m);
    sinv.resize(m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < p[i].size(); j++) {
        if (c[i] == c[p[i][j]])
          continue;
        sp[c[i]].push_back(c[p[i][j]]);
        sinv[c[p[i][j]]].push_back(c[i]);
      }
    }
  }
};

struct SAT {
  int n;
  vector<pair<int, int>> conjs;

  SAT() {
    n = 0;
  }

  // a \/ b
  void add_djs(int a, int b) {
    add_impl(-a, b);
    add_impl(-b, a);
  }

  // a /\ b
  void add_cjs(int a, int b) {
    add_impl(a, a);
    add_impl(b, b);
  }

  // a
  void add_lit(int a) {
    add_djs(a, a);
  }

  // a ^ b
  void add_xor(int a, int b) {
    add_djs(a, b);
    add_djs(-a, -b);
  }

  // a => b
  void add_impl(int a, int b) {
    n = max(n, max(abs(a), abs(b)));
    conjs.emplace_back(a, b);
  }

  // not(a \/ b)
  void add_nor(int a, int b) {
    add_cjs(-a, -b);
  }

  int f(int a) {
    assert(a != 0);
    if (a > 0) return a - 1;
    else return n + abs(a) - 1;
  }

  bool solve() {
    vector<vector<int>> p(2 * n), inv(2 * n);
    for (auto &c : conjs) {
      p[f(c.first)].push_back(f(c.second));
      inv[f(c.second)].push_back(f(c.first));
    }

    G g(2 * n, p, inv);
    g.solve();
    bool ok = true;
    for (int i = 0; i < n; i++) if (g.c[i] == g.c[i + n]) ok = false;
    return ok;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    r[i]++;
  }
  SAT solver;

  // p_1, .., p_2n : 左右
  vector<int> mp(2 * n);
  for (int i = 0; i < n; i++) {
    mp[2 * i] = i + 1;
    mp[2 * i + 1] = -(i + 1);
  }
  vector<pair<int, int>> ps(2 * n);
  for (int i = 0; i < n; i++) {
    ps[i * 2] = make_pair(l[i], r[i]);
    ps[i * 2 + 1] = make_pair(m - r[i], m - l[i]);
  }
  for (int i = 0; i < n * 2; i++) {
    for (int j = i + 1; j < 2 * n; j++) {
      if (i / 2 == j / 2) continue;
      if (!(ps[i].second <= ps[j].first || ps[j].second <= ps[i].first)) {
        solver.add_djs(-mp[i], -mp[j]);
      }
    }
  }

  if (solver.solve()) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}
0