Submission #5721696
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);
using ll = long long;
using pint = pair<int, int>;
using mint = map<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;
ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size();
s << '[';
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len-1) s << ", ";
}
s << ']';
return s;
}
struct aaa{
aaa(){
cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
};
}fastio;
class UnionFind {
public:
vector<ll> parent;
UnionFind(int n) {
parent = vector<ll>(n, -1);
}
int root(int a) {
if (parent[a] < 0) return a;
return parent[a] = root(parent[a]);
}
int size(int a) {
return -parent[root(a)];
}
bool same(int x, int y){
return root(x) == root(y);
}
bool unite(int a, int b) {
a = root(a);
b = root(b);
if (a == b) {
return false;
}
if (size(a) < size(b)) swap(a, b);
parent[a] += parent[b];
parent[b] = a;
return true;
}
};
int main(){
ll n, m;
cin >> n >> m;
UnionFind uf(n+m);
rep(i, n){
int k; cin >> k;
rep(j, k){
int l; cin >> l;
uf.unite(i, n-1+l);
}
}
rep(i, n-1){
if(!uf.same(i, i+1)){
NO();
return 0;
}
}
YES();
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
Laika |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2611 Byte |
Status |
AC |
Exec Time |
17 ms |
Memory |
1792 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
200 / 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, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
1 ms |
256 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
256 KB |
01-04.txt |
AC |
1 ms |
256 KB |
01-05.txt |
AC |
1 ms |
256 KB |
01-06.txt |
AC |
1 ms |
256 KB |
01-07.txt |
AC |
1 ms |
256 KB |
01-08.txt |
AC |
1 ms |
256 KB |
01-09.txt |
AC |
1 ms |
256 KB |
01-10.txt |
AC |
1 ms |
256 KB |
02-01.txt |
AC |
11 ms |
1024 KB |
02-02.txt |
AC |
14 ms |
1024 KB |
02-03.txt |
AC |
11 ms |
768 KB |
02-04.txt |
AC |
17 ms |
1536 KB |
02-05.txt |
AC |
15 ms |
1024 KB |
02-06.txt |
AC |
16 ms |
1664 KB |
02-07.txt |
AC |
16 ms |
1024 KB |
02-08.txt |
AC |
14 ms |
1024 KB |
02-09.txt |
AC |
16 ms |
1792 KB |
02-10.txt |
AC |
13 ms |
1024 KB |
02-11.txt |
AC |
13 ms |
1024 KB |
02-12.txt |
AC |
13 ms |
1152 KB |
02-13.txt |
AC |
13 ms |
1024 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |