Submission #993145


Source Code Expand

#include <bits/stdc++.h> // {{{
// clang-format off
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#pragma GCC target "tune=native,sse4.2"
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define USE1(T) template<typename T>inline
#define USE2(T, U) template<typename T,typename U>inline
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

template<typename T>using duo=std::pair<T,T>;
template<typename T>using vec=std::vector<T>;
using ll=long long;
using pii=duo<int>;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE1(T=int)vec<T>in(int n){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE1(T=int)vec<T>in(int n,T a){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>()+a);return v;}
USE1(T)vec<std::pair<T,int>>enume(const vec<T>&x,int s=0){int N=x.size();vec<std::pair<T,int>>v;v.reserve(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
#include <algorithm>
#include <vector>
namespace copr {
struct UF {
  std::vector<int> data;
  int groups;

  UF(int n) : data(n, -1), groups(n) {}
  bool unite(int a, int b, bool heuristic = true) {
    a = root(a);
    b = root(b);
    if (a != b) {
      groups--;
      if (heuristic && data[b] < data[a]) std::swap(a, b);
      data[a] += data[b];
      data[b] = a;
    }
    return a != b;
  }
  bool same(int a, int b) { return root(a) == root(b); }
  int root(int a) { return data[a] >= 0 ? data[a] = root(data[a]) : a; }
  int size(int a) { return -data[root(a)]; }
};
} // namespace copr
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

int w[100100];
int L[100100];

signed main() { //
  int N = rd(), M = rd();
  copr::UF uf(M);
  rep(i, N) {
    int K = rd();
    rep(j, K) { L[j] = rd() - 1; }
    rep(j, K) {
      w[L[j]]++;
      rep(k, j + 1, K) { uf.unite(L[j], L[k]); }
    }
  }
  int G = uf.groups;
  for (int i = 0; i < M; i++) {
    if (!w[i]) G--;
  }
  if (G == 1) {
    puts("YES");
  } else {
    puts("NO");
  }

  return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User orisano
Language C++14 (GCC 5.4.1)
Score 200
Code Size 3244 Byte
Status TLE
Exec Time 2102 ms
Memory 1024 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 0 / 200
Status
AC × 2
AC × 12
AC × 23
TLE × 2
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
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 2 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 3 ms 256 KB
01-07.txt AC 3 ms 256 KB
01-08.txt AC 3 ms 256 KB
01-09.txt AC 2 ms 256 KB
01-10.txt AC 2 ms 256 KB
02-01.txt AC 9 ms 1024 KB
02-02.txt AC 4 ms 256 KB
02-03.txt AC 7 ms 640 KB
02-04.txt AC 6 ms 1024 KB
02-05.txt AC 5 ms 384 KB
02-06.txt AC 7 ms 1024 KB
02-07.txt AC 5 ms 384 KB
02-08.txt AC 4 ms 256 KB
02-09.txt AC 5 ms 640 KB
02-10.txt TLE 2102 ms 640 KB
02-11.txt TLE 2102 ms 640 KB
02-12.txt AC 390 ms 640 KB
02-13.txt AC 396 ms 640 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB