CODE FESTIVAL 2016 Final

Submission #5433800

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct unionFind {
  int n;
  vector<int> pr;

  unionFind(){};
  unionFind(int _n) {
    n = _n;
    pr.resize(n, -1);
  };
  int root(int a) {
    if (pr[a] == -1)
      return a;
    else
      return pr[a] = root(pr[a]);
  }
  void unify(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return;
    pr[a] = b;
  }
  int same(int a, int b) { return root(a) == root(b); }
};

signed main() {
  int n, m;
  cin >> n >> m;
  vector<int> k(n);
  vector<vector<int>> l(n);
  vector<bool> used(m);

  for (int i = 0; i < n; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      int x;
      cin >> x;
      x--;
      l[i].push_back(x);
    }
  }
  unionFind uf(m);

  //   for (auto&& w : l) {
  //     for (auto&& v : w) cout << v << " ";
  //     cout << endl;
  //   }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k[i]; j++) {
      used[l[i][j]] = true;
      uf.unify(l[i][0], l[i][j]);
    }
  }
  int r = uf.root(l[0][0]);

  for (int i = 0; i < m; i++) {
    if (used[i]) {
      if (r != uf.root(i)) {
        cout << "No" << endl, exit(0);
      }
    }
  }
  cout << "Yes" << endl;
}

Submission

Task問題 C - Interpretation
User nameユーザ名 mnrutd
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1270 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 0 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt
dataset2 0 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,02-13.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt WA
01-02.txt WA
01-03.txt WA
01-04.txt WA
01-05.txt WA
01-06.txt WA
01-07.txt WA
01-08.txt WA
01-09.txt WA
01-10.txt WA
02-01.txt WA
02-02.txt WA
02-03.txt WA
02-04.txt WA
02-05.txt WA
02-06.txt WA
02-07.txt WA
02-08.txt WA
02-09.txt WA
02-10.txt WA
02-11.txt WA
02-12.txt WA
02-13.txt WA
sample-01.txt WA
sample-02.txt WA