Submission #1176838


Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

#define MAX_N 200000

class UnionFind {
private:
  // 親と木の深さ
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
public:
  void init(int n);
  int find(int x);
  void unite(int x, int y);
  bool same(int x, int y);
  int size(int n);
};

// 要素数nで初期化
void UnionFind::init (int n) {
  for(int i=0; i<n; i++) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素xの親を求める
int UnionFind::find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void UnionFind::unite(int x, int y) {
  // xとyの親
  x = find(x);
  y = find(y);
  if(x == y) return;

  // yのほうが深さが深い xの親はyの親
  if(rank[x] < rank[y]) {
    par[x] = y;
    s[y] = s[x] + s[y];
  }
  else {
    par[y] = x;
    s[x] = s[x] + s[y];
    if( rank[x] == rank[y] ) rank[x]++;
  }
}

// xとyが同じ集合に属するか
bool UnionFind::same(int x, int y) { return find(x) == find(y);}

int UnionFind::size(int n) {return s[find(n)];}

UnionFind b;
VI a[100010];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, n) {
    int k;
    cin >> k;
    REP(j, k) {
      int l;
      cin >> l;
      a[l].push_back(i);
    }
  }

  b.init(n+5);
  FOR(i, 1, m+1) {
    //cout << "i:" << i << endl;
    REP(j, a[i].size()-1) {
      //cout << a[i][j] << " " << a[i][j+1] << endl;
      b.unite(a[i][j], a[i][j+1]);
    }
  }
  //REP(i, n) cout << b.size(i) << " "; cout << endl;
  if(b.size(0) == n) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2154 Byte
Status AC
Exec Time 59 ms
Memory 6272 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 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 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
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 4352 KB
01-02.txt AC 3 ms 4352 KB
01-03.txt AC 3 ms 4352 KB
01-04.txt AC 3 ms 4352 KB
01-05.txt AC 3 ms 4352 KB
01-06.txt AC 3 ms 4352 KB
01-07.txt AC 3 ms 4352 KB
01-08.txt AC 3 ms 4352 KB
01-09.txt AC 3 ms 4352 KB
01-10.txt AC 3 ms 4352 KB
02-01.txt AC 48 ms 6272 KB
02-02.txt AC 49 ms 5120 KB
02-03.txt AC 48 ms 5760 KB
02-04.txt AC 59 ms 5760 KB
02-05.txt AC 54 ms 5248 KB
02-06.txt AC 58 ms 5760 KB
02-07.txt AC 56 ms 5248 KB
02-08.txt AC 39 ms 5092 KB
02-09.txt AC 57 ms 5112 KB
02-10.txt AC 51 ms 6144 KB
02-11.txt AC 50 ms 6144 KB
02-12.txt AC 50 ms 6016 KB
02-13.txt AC 49 ms 6016 KB
sample-01.txt AC 3 ms 4352 KB
sample-02.txt AC 3 ms 4352 KB