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 |
|
|
|
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 |