CODE FESTIVAL 2016 Final

Submission #5433888

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, false);

  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 (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状態 AC
Score得点 400
Source lengthソースコード長 1167 Byte
File nameファイル名
Exec time実行時間 54 ms
Memory usageメモリ使用量 7296 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 200 / 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 200 / 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 AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 2 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 2 ms 256 KB
01-07.txt AC 2 ms 256 KB
01-08.txt AC 2 ms 256 KB
01-09.txt AC 2 ms 256 KB
01-10.txt AC 2 ms 256 KB
02-01.txt AC 37 ms 2432 KB
02-02.txt AC 44 ms 6272 KB
02-03.txt AC 37 ms 2176 KB
02-04.txt AC 48 ms 4736 KB
02-05.txt AC 46 ms 5376 KB
02-06.txt AC 47 ms 4736 KB
02-07.txt AC 47 ms 6016 KB
02-08.txt AC 37 ms 6528 KB
02-09.txt AC 54 ms 7296 KB
02-10.txt AC 41 ms 4604 KB
02-11.txt AC 40 ms 4600 KB
02-12.txt AC 40 ms 4224 KB
02-13.txt AC 39 ms 4224 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB