結果

問題 No.274 The Wall
ユーザー goodbaton
提出日時 2018-04-10 11:21:20
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,051 ms / 2,000 ms
コード長 2,603 bytes
コンパイル時間 1,116 ms
コンパイル使用メモリ 104,872 KB
実行使用メモリ 261,120 KB
最終ジャッジ日時 2025-03-17 19:01:34
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:110:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |   scanf("%d%d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:113:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |     scanf("%d%d",l+i, r+i);
      |     ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

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