Submission #7555952
Source Code Expand
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> using namespace std; #define dump(x) cerr << #x << " = " << (x) << endl; #define PB push_back #define MP make_pair #define ll long long inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();} struct UnionFind { vector<int> par; UnionFind(int N) : par(N) { for(int i = 0; i < N; i++) par[i] = i; } int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; par[rx] = ry; } bool same(int x, int y) { int rx = root(x); int ry = root(y); return rx == ry; } }; int main(){ std::ios::sync_with_stdio(false); ll n, m; cin >> n >> m; UnionFind uf(m+1); ll k, tmp, prev = -1; ll need_bridge[m+1] = {}; for(int i=0;i<n;++i) { cin >> k; prev = -1; for(int j=0;j<k;++j) { cin >> tmp; if(prev != -1) { uf.unite(prev, tmp); } need_bridge[tmp] = 1; prev = tmp; } } ll root = -1; bool ret = true; // for(int i=1;i<=m;++i) // { // cerr << uf.root(i) << endl; // } for(int i=1;i<=m;++i) { if(need_bridge[i] == 1) { if(root == -1) { root = uf.root(i); } else { if(root != uf.root(i)) ret = false; } } } cout << (ret ? "YES" : "NO") << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Interpretation |
User | isa_rentacs |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2216 Byte |
Status | AC |
Exec Time | 16 ms |
Memory | 1408 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 | 15 ms | 1408 KB |
02-02.txt | AC | 13 ms | 256 KB |
02-03.txt | AC | 14 ms | 896 KB |
02-04.txt | AC | 16 ms | 1408 KB |
02-05.txt | AC | 14 ms | 384 KB |
02-06.txt | AC | 16 ms | 1408 KB |
02-07.txt | AC | 14 ms | 384 KB |
02-08.txt | AC | 12 ms | 256 KB |
02-09.txt | AC | 15 ms | 1408 KB |
02-10.txt | AC | 13 ms | 1280 KB |
02-11.txt | AC | 13 ms | 1280 KB |
02-12.txt | AC | 13 ms | 1024 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 |