Submission #6771437
Source Code Expand
// // main.cpp // #include <algorithm> #include <array> #include <assert.h> #include <iostream> #include <limits> #include <math.h> #include <memory> #include <memory> #include <queue> #include <random> #include <set> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; using ll = long long; using ull = unsigned long long; struct UnionFind { vector<size_t> parent; vector<size_t> rank; size_t find_parent(size_t x) { if (parent[x] == x) { return x; } else { parent[x] = find_parent(parent[x]); return parent[x]; } } explicit UnionFind(size_t size) { parent.resize(size); rank.resize(size); for (size_t i = 0; i < size; i++) { parent[i] = i; rank[i] = 0; } } virtual ~UnionFind() {} void unite(size_t x, size_t y) { size_t px = find_parent(x); size_t py = find_parent(y); if (px == py) { return; } if (rank[px] < rank[py]) { parent[px] = py; } else if (rank[px] > rank[py]) { parent[py] = px; } else { // rank[px] == rank[py] parent[py] = px; rank[px]++; } } bool is_same(size_t x, size_t y) { return find_parent(x) == find_parent(y); } unordered_map<size_t, set<size_t>> create_map_parent_to_elements() { unordered_map<size_t, set<size_t>> ans; for (size_t i = 0; i < parent.size(); i++) { ans[find_parent(i)].insert(i); } return ans; } }; int main() { int N, M; cin >> N >> M; UnionFind uf(N + M); for (int i = 0; i < N; i++) { int Ki; cin >> Ki; for (int j = 0; j < Ki; j++) { int Lj; cin >> Lj; Lj--; uf.unite(i, N + Lj); } } for (int i = 0; i < N; i++) { if (!uf.is_same(0, i)) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | tttmmm |
Language | C++14 (Clang 3.8.0) |
Score | 400 |
Code Size | 1991 Byte |
Status | AC |
Exec Time | 126 ms |
Memory | 3328 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 | 2 ms | 256 KB |
01-03.txt | AC | 2 ms | 256 KB |
01-04.txt | AC | 2 ms | 256 KB |
01-05.txt | AC | 2 ms | 256 KB |
01-06.txt | AC | 2 ms | 256 KB |
01-07.txt | AC | 2 ms | 256 KB |
01-08.txt | AC | 2 ms | 256 KB |
01-09.txt | AC | 2 ms | 256 KB |
01-10.txt | AC | 2 ms | 256 KB |
02-01.txt | AC | 85 ms | 1920 KB |
02-02.txt | AC | 110 ms | 1792 KB |
02-03.txt | AC | 88 ms | 1152 KB |
02-04.txt | AC | 111 ms | 2688 KB |
02-05.txt | AC | 112 ms | 1664 KB |
02-06.txt | AC | 110 ms | 2688 KB |
02-07.txt | AC | 117 ms | 1792 KB |
02-08.txt | AC | 93 ms | 1792 KB |
02-09.txt | AC | 126 ms | 3328 KB |
02-10.txt | AC | 101 ms | 1792 KB |
02-11.txt | AC | 101 ms | 1792 KB |
02-12.txt | AC | 100 ms | 1792 KB |
02-13.txt | AC | 99 ms | 1792 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |