結果

問題 No.274 The Wall
ユーザー goodbaton
提出日時 2019-01-16 11:55:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 956 ms / 2,000 ms
コード長 3,458 bytes
コンパイル時間 1,288 ms
コンパイル使用メモリ 113,376 KB
実行使用メモリ 263,120 KB
最終ジャッジ日時 2024-06-22 02:26:04
合計ジャッジ時間 4,059 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


// int main(){
// 
// 
//   return 0;
// }

/* Strongly Connected Component */

/*
 1. dfsをして、戻るときに1から順に番号を付ける
 2. 数値が大きいノードから逆辺を使ってdfsをする。
    すでに訪れているノードには行かない。
    たどり着けるノードが同じ連結成分に属する。
 */

struct SCC{
  int n;
  vector<vector<int> > G, rG;
  vector<int> vs, cmp;
  vector<bool> used;
  
  SCC(int n):n(n), G(n), rG(n), cmp(n){}
  
  void add_edge(int from, int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  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);
  }

  int solve(){
    used.assign(n, false);
    vs.clear();
    for(int i=0;i<n;i++)
      if(!used[i]) dfs(i);
    used.assign(n, false);
    int k = 0;
    for(int i=vs.size()-1; i>=0; i--)
      if(!used[vs[i]]) rdfs(vs[i], k++);
    return k; //強連結成分数
  }

  //属する強連結成分番号(トポロジカル順)
  int operator[](int k) const {
    return cmp[k];
  }
};

/* 2-SAT (Source: 蟻本)*/

struct TwoSAT{
  int n;
  SCC scc;
  vector<bool> ans;
  
  TwoSAT(int n):n(n), scc(n*2), ans(n) {}

  //1-index, add(1, -2) -> p or not q
  void add(int a, int b){
    a = a > 0 ? a - 1 : n - a - 1;
    b = b > 0 ? b - 1 : n - b - 1;
    scc.add_edge((a + n) % (2 * n), b);
    scc.add_edge((b + n) % (2 * n), a);
  }

  bool solve(){
    scc.solve();
    for(int i=0; i<n; i++)
      if(scc.cmp[i] == scc.cmp[n+i]) return false;

    for(int i=0; i<n; i++)
      ans[i] = scc.cmp[i] > scc.cmp[n+i];
    return true;
  }
};

int main(){
  int n, m;
  int l[SIZE], r[SIZE], rl[SIZE], rr[SIZE];

  scanf("%d%d", &n, &m);

  for (int i=0; i<n; i++) {
    scanf("%d%d", l+i, r+i);
    rl[i] = m - 1 - r[i];
    rr[i] = m - 1 - l[i];
  }

  TwoSAT sat(n);

  for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) {
      if (i == j) continue;
      if (!( r[j] <  l[i] ||  r[i] <  l[j])) sat.add(-(i+1), -(j+1));
      if (!(rr[j] <  l[i] ||  r[i] < rl[j])) sat.add(-(i+1), j+1);
      if (!( r[j] < rl[i] || rr[i] <  l[j])) sat.add(i+1, -(j+1));
      if (!(rr[j] < rl[i] || rr[i] < rl[j])) sat.add(i+1, j+1);
    }
  }

  puts(sat.solve() ? "YES": "NO");

  return 0;
}
0