Submission #992388


Source Code Expand

#include"bits/stdc++.h"
using namespace std;

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

class UnionFind {
private:
	std::vector<int> data_array;
	const int root(int id) {
		if (data_array[id] >= 0)
			return data_array[id] = root(data_array[id]);
		else
			return id;
	}
public:
	UnionFind(size_t size) : data_array(size, -1) {}
	// unionは予約語
	bool union_(int lhs, int rhs) {
		lhs = root(lhs);
		rhs = root(rhs);
		bool is_union = (lhs != rhs);
		if (is_union) {
			if (data_array[lhs] > data_array[rhs]) { std::swap(lhs, rhs); }
			data_array[lhs] += data_array[rhs];
			data_array[rhs] = lhs;
		}
		return is_union;
	}
	bool find(int lhs, int rhs) {
		return (root(lhs) == root(rhs));
	}
};


int main() {
	int n, m;
	cin >> n >> m;
	vector<int> k(n);
	vector<vector<int>> l(n);
	for (int i = 0; i < n; i++) {
		cin >> k[i];
		for (int j = 0; j < k[i]; j++) {
			int x;
			cin >> x;
			x--;
			l[i].push_back(x);
		}
	}

	UnionFind u(n + m);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <k[i]; j++) {
			u.union_(i, n + l[i][j]);
		}
	}

	bool isok = true;
	for (int i = 0; i < n; i++) {
		isok &= u.find(i, 0);
	}
	if (isok) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Submission Info

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

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 25
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 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 3 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 3 ms 256 KB
01-10.txt AC 3 ms 256 KB
02-01.txt AC 36 ms 1408 KB
02-02.txt AC 52 ms 6272 KB
02-03.txt AC 37 ms 1408 KB
02-04.txt AC 51 ms 4096 KB
02-05.txt AC 51 ms 5248 KB
02-06.txt AC 51 ms 4096 KB
02-07.txt AC 53 ms 5888 KB
02-08.txt AC 44 ms 6528 KB
02-09.txt AC 59 ms 6912 KB
02-10.txt AC 45 ms 3712 KB
02-11.txt AC 45 ms 3708 KB
02-12.txt AC 43 ms 3840 KB
02-13.txt AC 43 ms 3840 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 3 ms 256 KB