Submission #13478380


Source Code Expand

Copy
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

struct UnionFind {
  vi par, count;

  UnionFind(int N) : par(N), count(N, 1){
    for(int i = 0; i < N; i++) par.at(i) = i;
  }

  int root(int x){
    if(par.at(x) == x) return x;
    return par.at(x) = root(par.at(x));
  }

  int unite(int x, int y){
    if(root(x) == root(y)) return 0;
    if(size(x) < size(y)){
      count.at(root(y)) += count.at(root(x));
      par.at(root(x)) = root(y);
    }
    else{
      count.at(root(x)) += count.at(root(y));
      par.at(root(y)) = root(x);
    }
    return 1;
  }

  bool same(int x, int y){
    return root(x) == root(y);
  }

  int size(int x){
    return count.at(root(x));
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N, M;
  cin >> N >> M;
  vvll A(M, vll(0));
  for(int i = 0; i < N; i++){
    ll K;
    cin >> K;
    for(int j = 0; j < K; j++){
      ll L;
      cin >> L;
      L--;
      A.at(L).push_back(i);
    }
  }
  UnionFind uf(N);
  for(int i = 0; i < M; i++){
    for(int j = 0; j < sz(A.at(i)); j++){
      uf.unite(A.at(i).at(0), A.at(i).at(j));
    }
  }
  if(uf.size(0) == N) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Submission Info

Submission Time
Task C - Interpretation
User grf
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1869 Byte
Status
Exec Time 26 ms
Memory 4736 KB

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 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
Case Name Status Exec Time Memory
01-01.txt 1 ms 256 KB
01-02.txt 1 ms 256 KB
01-03.txt 1 ms 256 KB
01-04.txt 1 ms 256 KB
01-05.txt 1 ms 256 KB
01-06.txt 1 ms 256 KB
01-07.txt 1 ms 256 KB
01-08.txt 1 ms 256 KB
01-09.txt 1 ms 256 KB
01-10.txt 1 ms 256 KB
02-01.txt 22 ms 4736 KB
02-02.txt 17 ms 2176 KB
02-03.txt 19 ms 3200 KB
02-04.txt 26 ms 4736 KB
02-05.txt 21 ms 2560 KB
02-06.txt 24 ms 4736 KB
02-07.txt 22 ms 2560 KB
02-08.txt 15 ms 1992 KB
02-09.txt 18 ms 4212 KB
02-10.txt 16 ms 3832 KB
02-11.txt 16 ms 3832 KB
02-12.txt 18 ms 3840 KB
02-13.txt 18 ms 3712 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB