結果

問題 No.274 The Wall
ユーザー goodbatongoodbaton
提出日時 2018-04-10 11:21:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 966 ms / 2,000 ms
コード長 2,603 bytes
コンパイル時間 859 ms
コンパイル使用メモリ 101,048 KB
実行使用メモリ 260,876 KB
最終ジャッジ日時 2023-09-04 02:31:19
合計ジャッジ時間 4,144 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 316 ms
127,148 KB
testcase_04 AC 1 ms
4,380 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,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 966 ms
260,876 KB
testcase_12 AC 15 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 7 ms
4,376 KB
testcase_15 AC 17 ms
4,380 KB
testcase_16 AC 219 ms
71,228 KB
testcase_17 AC 209 ms
67,804 KB
testcase_18 AC 230 ms
73,264 KB
testcase_19 AC 31 ms
4,376 KB
testcase_20 AC 36 ms
4,380 KB
testcase_21 AC 37 ms
4,380 KB
testcase_22 AC 40 ms
4,380 KB
testcase_23 AC 40 ms
4,376 KB
testcase_24 AC 40 ms
4,380 KB
testcase_25 AC 40 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


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

struct SCC{
  int n;
  vector<vector<int> > G, rG;
  vector<int> vs;
  vector<bool> used;
  vector<int> cmp; //属する強連結成分番号(トポロジカル順)

  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; //強連結成分数
  }
};

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

/*
  A => B ... not A or B
 */


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