Submission #991868


Source Code Expand

#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ld = long double;
const ld eps = 1e-9;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};
int main() {
	int N, M; cin >> N >> M;
	UnionFind uf(M);
	vector<int>used(M);
	for (int i = 0; i < N; ++i) {
		int K; cin >> K;
		set<int>roots;
		vector<int>connects;
		for (int j = 0; j < K; ++j) {
			int l; cin >> l; l--;
			int r = uf.root(l);
			if (roots.find(r) == roots.end()) {
				roots.emplace(r);
				connects.push_back(l);
			}
			used[l] = true;
		}
		for (int j = 0;j <int( connects.size()) - 1; ++j) {
			uf.unionSet(connects[j], connects[j + 1]);
		}
	}
	set<int>aset;
	for (int i = 0; i < M; ++i) {
		if (used[i]) {
			aset.emplace(uf.root(i));
		}
	}
	if (aset.size() == 1) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User yuma000
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1311 Byte
Status AC
Exec Time 60 ms
Memory 3196 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 2 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 384 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 43 ms 1024 KB
02-02.txt AC 47 ms 256 KB
02-03.txt AC 41 ms 640 KB
02-04.txt AC 52 ms 1024 KB
02-05.txt AC 50 ms 384 KB
02-06.txt AC 53 ms 1024 KB
02-07.txt AC 50 ms 256 KB
02-08.txt AC 41 ms 256 KB
02-09.txt AC 56 ms 1024 KB
02-10.txt AC 59 ms 3196 KB
02-11.txt AC 60 ms 3196 KB
02-12.txt AC 54 ms 896 KB
02-13.txt AC 55 ms 896 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB