結果

問題 No.274 The Wall
ユーザー goodbatongoodbaton
提出日時 2018-04-10 11:10:01
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,693 bytes
コンパイル時間 1,062 ms
コンパイル使用メモリ 101,256 KB
実行使用メモリ 148,352 KB
最終ジャッジ日時 2024-06-26 20:53:02
合計ジャッジ時間 4,161 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 269 ms
77,696 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 WA -
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 831 ms
148,352 KB
testcase_12 AC 15 ms
6,944 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 231 ms
53,248 KB
testcase_17 AC 211 ms
51,072 KB
testcase_18 AC 229 ms
54,400 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 54 ms
16,768 KB
testcase_23 AC 55 ms
16,640 KB
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:115:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  115 |   scanf("%d%d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:118:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |     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

bool connect[SIZE*2][SIZE*2];

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){
    if(connect[from][to]) return;
    connect[from][to] = true;
    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[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