結果

問題 No.274 The Wall
コンテスト
ユーザー yuppe19 😺
提出日時 2015-09-06 17:37:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,061 bytes
コンパイル時間 526 ms
コンパイル使用メモリ 52,060 KB
最終ジャッジ日時 2024-11-14 19:10:23
合計ジャッジ時間 1,109 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:9:1: error: ‘vector’ does not name a type
    9 | vector<vector<int>> G1, G2;
      | ^~~~~~
main.cpp:10:1: error: ‘vector’ does not name a type
   10 | vector<bool> visited;
      | ^~~~~~
main.cpp:11:1: error: ‘vector’ does not name a type
   11 | vector<int> cmp, stk;
      | ^~~~~~
main.cpp: In function ‘void nya(int)’:
main.cpp:14:3: error: ‘visited’ was not declared in this scope
   14 |   visited[v] = true;
      |   ^~~~~~~
main.cpp:15:16: error: ‘G1’ was not declared in this scope
   15 |   for(int vv : G1[v]) {
      |                ^~
main.cpp:19:3: error: ‘stk’ was not declared in this scope; did you mean ‘std’?
   19 |   stk.push_back(v);
      |   ^~~
      |   std
main.cpp: In function ‘void nyaa(int, int)’:
main.cpp:23:3: error: ‘visited’ was not declared in this scope
   23 |   visited[v] = true;
      |   ^~~~~~~
main.cpp:24:16: error: ‘G2’ was not declared in this scope
   24 |   for(int vv : G2[v]) {
      |                ^~
main.cpp:28:3: error: ‘cmp’ was not declared in this scope
   28 |   cmp[v] = cnt;
      |   ^~~
main.cpp: In function ‘int scc()’:
main.cpp:32:3: error: ‘visited’ was not declared in this scope
   32 |   visited.assign(N, false);
      |   ^~~~~~~
main.cpp:33:3: error: ‘cmp’ was not declared in this scope
   33 |   cmp.assign(N, 0);
      |   ^~~
main.cpp:34:3: error: ‘stk’ was not declared in this scope; did you mean ‘std’?
   34 |   stk.clear();
      |   ^~~
      |   std
main.cpp: In function ‘void add_edge(int, int)’:
main.cpp:50:3: error: ‘G1’ was not declared in this scope; did you mean ‘v1’?
   50 |   G1[v0].push_back(v1);
      |   ^~
      |   v1
main.cpp:51:3: error: ‘G2’ was not declared in this scope
   51 |   G2[v1].push_back(v0);
      |   ^~
main.cpp: In function ‘int main()’:
main.cpp:65:3: error: ‘vector’ was not declared in this scope
   65 |   vector<int> l(n), r(n);
      |   ^~~~~~
main.cpp:3:1: note:

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

int n, m, N;
vector<vector<int>> G1, G2;
vector<bool> visited;
vector<int> cmp, stk;

void nya(int v) {
  visited[v] = true;
  for(int vv : G1[v]) {
    if(visited[vv]) { continue; }
    nya(vv);
  }
  stk.push_back(v);
}

void nyaa(int v, int cnt) {
  visited[v] = true;
  for(int vv : G2[v]) {
    if(visited[vv]) { continue; }
    nyaa(vv, cnt);
  }
  cmp[v] = cnt;
}

int scc() {
  visited.assign(N, false);
  cmp.assign(N, 0);
  stk.clear();
  for(int v : range(N)) {
    if(visited[v]) { continue; }
    nya(v);
  }
  visited.assign(N, false);
  int cnt = 0;
  while(!stk.empty()) {
    int v = stk.back(); stk.pop_back();
    if(visited[v]) { continue; }
    nyaa(v, cnt++);
  }
  return cnt;
}

void add_edge(int v0, int v1) {
  G1[v0].push_back(v1);
  G2[v1].push_back(v0);
}

void add_edges(int i, int j) {
  add_edge(i, j);
  int x = i>=n ? i-n : i+n,
      y = j>=n ? j-n : j+n;
  add_edge(y, x);
}

int rev(int x) { return m-x-1; }

int main(void) {
  scanf("%d%d", &n, &m);
  vector<int> l(n), r(n);
  for(int i : range(n)) {
    scanf("%d%d", &l[i], &r[i]);
  }
  N = 2 * n;
  G1.assign(N, vector<int>());
  G2.assign(N, vector<int>());
  for(int i : range(n)) {
    int li0 = l[i], li1 = rev(r[i]),
        ri0 = r[i], ri1 = rev(l[i]);
    for(int j : range(i+1, n)) {
      int lj0 = l[j], lj1 = rev(r[j]),
          rj0 = r[j], rj1 = rev(l[j]);
      if(li0 <= rj0 && lj0 <= ri0) { add_edges(i,   n+j); }
      if(li1 <= rj0 && lj0 <= ri1) { add_edges(n+i, n+j); }
      if(li0 <= rj1 && lj1 <= ri0) { add_edges(i,   j  ); }
      if(li1 <= rj1 && lj1 <= ri1) { add_edges(n+i, j  ); }
    }
  }
  scc();
  for(int i : range(n)) {
    if(cmp[i] == cmp[n+i]) {
      puts("NO");
      return 0;
    }
  }
  puts("YES");
  return 0;
}
0