Submission #5776006
Source Code Expand
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;
#define MOD 1000000007
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
struct Edge {//グラフ
ll to, cap, rev;
Edge(ll _to, ll _cap, ll _rev) {
to = _to; cap = _cap; rev = _rev;
}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {//最大フロー求める Ford-fulkerson
G[from].push_back(Edge(to, cap, (ll)G[to].size()));
if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));//最小カットの場合逆辺は0にする
}
ll max_flow_dfs(Graph & G, ll v, ll t, ll f, vector<bool> & used)
{
if (v == t)
return f;
used[v] = true;
for (int i = 0; i < G[v].size(); ++i) {
Edge& e = G[v][i];
if (!used[e.to] && e.cap > 0) {
ll d = max_flow_dfs(G, e.to, t, min(f, e.cap), used);
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
ll max_flow(Graph & G, ll s, ll t)
{
ll flow = 0;
for (;;) {
vector<bool> used(G.size());
REP(i, used.size())used[i] = false;
ll f = max_flow_dfs(G, s, t, INF, used);
if (f == 0) {
return flow;
}
flow += f;
}
}
void BellmanFord(Graph& G, ll s, Array& d, Array &negative) {//O(|E||V|)
d.resize(G.size());
negative.resize(G.size());
REP(i, d.size())d[i] = INF;
REP(i, d.size())negative[i] = false;
d[s] = 0;
REP(k, G.size() - 2) {
REP(i, G.size()) {
REP(j, G[i].size()) {
if (d[G[i][j].to] > d[i] + G[i][j].cap) {
d[G[i][j].to] = d[i] + G[i][j].cap;
}
}
}
}
REP(k, G.size() - 2) {
REP(i, G.size()) {
REP(j, G[i].size()) {
if (d[G[i][j].to] > d[i] + G[i][j].cap) {
d[G[i][j].to] = d[i] + G[i][j].cap;
negative[G[i][j].to] = true;
}
if (negative[i] == true)negative[G[i][j].to] = true;
}
}
}
}
void Dijkstra(Graph& G, ll s, Array& d) {//O(|E|log|V|)
d.resize(G.size());
REP(i, d.size())d[i] = INF;
d[s] = 0;
priority_queue<P, vector<P>, greater<P>> q;
q.push(make_pair(0, s));
while (!q.empty()) {
P a = q.top();
q.pop();
if (d[a.second] < a.first)continue;
REP(i, G[a.second].size()) {
Edge e = G[a.second][i];
if (d[e.to] > d[a.second] + e.cap) {
d[e.to] = d[a.second] + e.cap;
q.push(make_pair(d[e.to], e.to));
}
}
}
}
void WarshallFloyd(Graph& G, Matrix& d) {
d.resize(G.size());
REP(i, d.size())d[i].resize(G.size());
REP(i, d.size()) {
REP(j, d[i].size()) {
d[i][j] = INF;
}
}
REP(i, G.size()) {
d[i][i] = 0;
}
REP(i, G.size()) {
REP(j, G[i].size()) {
d[i][G[i][j].to] = G[i][j].cap;
}
}
REP(i, G.size()) {
REP(j, G.size()) {
REP(k, G.size()) {
chmin(d[j][k], d[j][i] + d[i][k]);
}
}
}
}
class UnionFind {
vector<int> data;
public:
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)];
}
};
//約数求める //約数
void divisor(ll n, vector<ll>& ret) {
for (ll i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end());
}
//nCrとか
class Combination {
public:
Array fact;
Array inv;
ll mod;
ll mod_inv(ll x) {
ll n = mod - 2;
ll res = 1LL;
while (n > 0) {
if (n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
ll nCr(ll n, ll r) {
return ((fact[n] * inv[r] % mod) * inv[n - r]) % mod;
}
ll nPr(ll n, ll r) {
return (fact[n] * inv[n - r]) % mod;
}
Combination(ll n, ll _mod) {
mod = _mod;
fact.resize(n + 1);
fact[0] = 1;
REP(i, n) {
fact[i + 1] = (fact[i] * (i + 1LL)) % mod;
}
inv.resize(n + 1);
REP(i, n + 1) {
inv[i] = mod_inv(fact[i]);
}
}
};
ll gcd(ll m, ll n) {
if (n == 0)return m;
return gcd(n, m % n);
}//gcd
ll lcm(ll m, ll n) {
return m / gcd(m, n) * n;
}
int main() {
ll n, m;
cin >> n >> m;
UnionFind uni(m + 1);
map<ll, ll> ma;
REP(i, n) {
ll k;
cin >> k;
ll l;
cin >> l;
ma[l]++;
REP(j, k-1) {
ll l2;
cin >> l2;
ma[l2]++;
uni.unionSet(l, l2);
}
}
auto itr = ma.begin();
ll root = uni.root(itr->first);
for (auto itr2 : ma) {
if (root != uni.root(itr2.first)) {
cout << "NO";
return 0;
}
}
cout << "YES";
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
tran0826 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
5448 Byte |
Status |
AC |
Exec Time |
65 ms |
Memory |
4608 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 |
2 ms |
256 KB |
01-04.txt |
AC |
1 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 |
62 ms |
4608 KB |
02-02.txt |
AC |
43 ms |
256 KB |
02-03.txt |
AC |
56 ms |
3200 KB |
02-04.txt |
AC |
65 ms |
3328 KB |
02-05.txt |
AC |
52 ms |
896 KB |
02-06.txt |
AC |
65 ms |
3328 KB |
02-07.txt |
AC |
53 ms |
896 KB |
02-08.txt |
AC |
31 ms |
256 KB |
02-09.txt |
AC |
45 ms |
640 KB |
02-10.txt |
AC |
52 ms |
3584 KB |
02-11.txt |
AC |
53 ms |
3584 KB |
02-12.txt |
AC |
51 ms |
3200 KB |
02-13.txt |
AC |
51 ms |
3200 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |