結果

問題 No.274 The Wall
ユーザー どらら
提出日時 2018-12-18 01:59:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 2,839 bytes
コンパイル時間 1,920 ms
コンパイル使用メモリ 177,500 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-17 19:02:02
合計ジャッジ時間 3,236 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, n) for (int i = (a); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, c) \
  for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

class Solver2SAT {
  std::vector<std::vector<int>> G, rG;
  std::vector<int> vs;
  std::vector<bool> used;
  std::vector<int> cmp;

  void dfs(int v) {
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++)
      if (!used[G[v][i]]) dfs(G[v][i]);
    vs.push_back(v);
  }

  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++)
      if (!used[rG[v][i]]) rdfs(rG[v][i], k);
  }

  void clear() {
    G.clear();
    rG.clear();
    vs.clear();
    used.clear();
    cmp.clear();
  }

  int scc() {
    for (int v = 0; v < G.size(); v++)
      if (!used[v]) dfs(v);
    used.clear();
    used.resize(G.size(), false);
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; i--)
      if (!used[vs[i]]) rdfs(vs[i], k++);
    return k;
  }

 public:
  void init(int N) {
    clear();
    G.resize(N);
    rG.resize(N);
    used.resize(N, false);
    cmp.resize(N, 0);
  }

  void add_edge(int from, int to) {
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  std::vector<bool> solve() {
    scc();
    for (int i = 0; i < G.size() / 2; i++) {
      if (cmp[i] == cmp[G.size() / 2 + i]) return std::vector<bool>();
    }
    std::vector<bool> ret(G.size() / 2);
    for (int i = 0; i < G.size() / 2; i++) {
      if (cmp[i] > cmp[G.size() / 2 + i])
        ret[i] = true;
      else
        ret[i] = false;
    }
    return ret;
  }
};

bool check(int li, int ri, int lj, int rj) {
  return (li <= lj && lj <= ri) || (li <= rj && rj <= ri) ||
         (lj <= li && li <= rj) || (lj <= ri && ri <= rj);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> v;
  rep(i, N) {
    int l, r;
    cin >> l >> r;
    v.push_back({l, r});
  }

  Solver2SAT sat;
  sat.init(2 * N);
  rep(i, N) {
    REP(j, i + 1, N) {
      int a = i;
      int na = N + i;
      int b = j;
      int nb = N + j;
      bool flgTT = check(v[i][0], v[i][1], v[j][0], v[j][1]);
      bool flgFT = check(M - 1 - v[i][1], M - 1 - v[i][0], v[j][0], v[j][1]);

      if (flgTT && flgFT) {
        cout << "NO" << endl;
        return 0;
      } else if (flgTT) {
        sat.add_edge(na, b);
        sat.add_edge(nb, a);
        sat.add_edge(a, nb);
        sat.add_edge(b, na);
      } else if (flgFT) {
        sat.add_edge(na, nb);
        sat.add_edge(b, a);
        sat.add_edge(a, b);
        sat.add_edge(nb, na);
      }
    }
  }
  vector<bool> ret = sat.solve();
  if (ret.size() != 0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}
0