結果

問題 No.483 マッチ並べ
ユーザー yuppe19 😺yuppe19 😺
提出日時 2017-02-16 17:15:03
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,111 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 69,740 KB
最終ジャッジ日時 2024-04-27 02:25:01
合計ジャッジ時間 770 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:54:1: error: ‘vector’ does not name a type
   54 | vector<vector<int>> G;
      | ^~~~~~
main.cpp:55:1: error: ‘vector’ does not name a type
   55 | vector<bool> seen;
      | ^~~~~~
main.cpp: In function ‘void rec(int)’:
main.cpp:59:6: error: ‘seen’ was not declared in this scope
   59 |   if(seen[i]) { return; }
      |      ^~~~
main.cpp:60:3: error: ‘seen’ was not declared in this scope
   60 |   seen[i] = true;
      |   ^~~~
main.cpp:61:15: error: ‘G’ was not declared in this scope
   61 |   for(int j : G[i]) {
      |               ^
main.cpp: In function ‘int main()’:
main.cpp:70:3: error: ‘G’ was not declared in this scope
   70 |   G.assign(N*N, vector<int>());
      |   ^
main.cpp:70:17: error: ‘vector’ was not declared in this scope
   70 |   G.assign(N*N, vector<int>());
      |                 ^~~~~~
main.cpp:5:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    4 | #include <map>
  +++ |+#include <vector>
    5 | using namespace std;
main.cpp:70:24: error: expected primary-expression before ‘int’
   70 |   G.assign(N*N, vector<int>());
      |                        ^~~
main.cpp:71:3: error: ‘seen’ was not declared in this scope
   71 |   seen.assign(N*N, false);
      |   ^~~~
main.cpp:73:23: error: expected primary-expression before ‘>’ token
   73 |   vector<pair<int, int>> memo;
      |                       ^~
main.cpp:73:26: error: ‘memo’ was not declared in this scope
   73 |   vector<pair<int, int>> memo;
      |                          ^~~~
main.cpp:69:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
main.cpp:75:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |     int r0, c

ソースコード

diff # 

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

// union-find に値を持たせる
struct UnionFind {
  UnionFind() {};
  void unite(int, int);
  int find(int);
  bool contains(int x);
  int size_of(int x);
  int evaluate(int x);
  set<int> key_set(); // parのkeySet
  map<int, int> val;
private:
  map<int, int> par;
};

int UnionFind::find(int x) {
  if(!contains(x)) { par[x] = -1; }
  return par[x] < 0 ? x : (par[x] = find(par[x]));
}

int UnionFind::evaluate(int x) {
  return val[find(x)];
}

void UnionFind::unite(int x, int y) {
  x = find(x), y = find(y);
  if(x == y) { return; }
  if(par[x] > par[y]) { swap(x, y); }
  par[x] += par[y];
  par[y] = x;
  val[x] = val[y] = val[x] + val[y]; // add
}

bool UnionFind::contains(int x) {
  return par.count(x);
}

set<int> UnionFind::key_set() {
  set<int> keySet;
  for(auto&& kv : par) {
    keySet.insert(kv.first);
  }
  return keySet;
}

int UnionFind::size_of(int x) { return -par[find(x)]; }

///
vector<vector<int>> G;
vector<bool> seen;
UnionFind uf;

void rec(int i) {
  if(seen[i]) { return; }
  seen[i] = true;
  for(int j : G[i]) {
    ++uf.val[j]; // 入次数をUnionFindの値として持つ
    rec(j);
  }
}

int main(void) {
  constexpr int N = 111;
  int n; scanf("%d", &n);
  G.assign(N*N, vector<int>());
  seen.assign(N*N, false);
  set<int> vs;
  vector<pair<int, int>> memo;
  for(int i=0; i<n; ++i) {
    int r0, c0, r1, c1; scanf("%d%d%d%d", &r0, &c0, &r1, &c1);
    int x = r0 * N + c0,
        y = r1 * N + c1;
    G[x].push_back(y);
    memo.emplace_back(x, y);
    vs.insert(x);
    vs.insert(y);
  }

  for(int v : vs) {
    rec(v);
  }

  // 値を持たせてから unite したい
  for(auto&& xy : memo) {
    int x, y; tie(x, y) = xy;
    uf.unite(x, y);
  }

  for(int k : uf.key_set()) {
    // 連結なグラフごとのループ
    int size = uf.size_of(k);
    int V = size; // 連結なグラフの頂点数
    int E = uf.evaluate(k); // 連結なグラフの総入次数
    if(V < E) {
      puts("NO");
      return 0;
    }
  }
  puts("YES");

  return 0;
}
0