Submission #1801794
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define LL long long
void disp(vector<int> v){
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
cout<<endl;
}
template <typename T>
class undigraph {
public:
struct edge{
int from;
int to;
T cost;
};
vector< vector<int> > v;
vector<edge> edges;
int n;
undigraph(int n){
v.resize(n);
}
void add(int from,int to,T cost = 1){
v[from].push_back(edges.size());
v[to].push_back(edges.size());
edges.push_back({from, to, cost});
}
};
template <typename T>
vector <T> dijkstra(const undigraph<T> &g, int start) {
vector<T> dist(g.n, numeric_limits<T>::max());
priority_queue<pair<T, int>, vector<pair<T, int> >, greater<pair<T, int> > > s;
dist[start] = 0;
s.emplace(dist[start], start);
while(!s.empty()){
int expected = s.top().first;
int base = s.top().second;
if(expected != dist[base]){
continue;
}
s.pop();
for(int id:g.v[base]){
auto &e = g.edges[id];
int to = base ^ e.from ^ e.to;
if(dist[base] + e.cost < dist[to]){
dist[to] = dist[base] + e.cost;
s.emplace(dist[to],to);
}
}
}
return dist;
}
#define MAX_N 100000
int par[MAX_N],rnk[MAX_N];
void init(int n){
REP(i,n){
par[i]=i;
rnk[i]=0;
}
}
int root(int x){
return par[x]==x?x:par[x]=root(par[x]);
}
bool same(int x,int y){
return root(x)==root(y);
}
void unite(int x,int y){
x=root(x);
y=root(y);
if(x==y)
return;
if(rnk[x]<rnk[y]){
par[x]=y;
}else{
par[y]=x;
if(rnk[x]==rnk[y]) rnk[x]++;
}
}
vector<vector<int>> v;
int main(){
int n,m,k,l;
cin>>n>>m;
v.resize(m);
init(n);
REP(i,n){
cin>>k;
REP(j,k){
cin>>l;
l--;
v[l].push_back(i);
}
}
REP(i,m){
FOR(j,1,v[i].size()){
unite(v[i][0],v[i][j]);
}
}
REP(i,n){
if(!same(0,i)){
cout<<"NO"<<endl;
return 1;
}
}
cout<<"YES"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
penpenpen |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2281 Byte |
Status |
RE |
Exec Time |
61 ms |
Memory |
4608 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 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 |
RE |
2 ms |
256 KB |
01-04.txt |
AC |
2 ms |
256 KB |
01-05.txt |
RE |
2 ms |
256 KB |
01-06.txt |
AC |
2 ms |
256 KB |
01-07.txt |
AC |
2 ms |
256 KB |
01-08.txt |
RE |
2 ms |
256 KB |
01-09.txt |
AC |
2 ms |
256 KB |
01-10.txt |
AC |
2 ms |
256 KB |
02-01.txt |
AC |
50 ms |
4608 KB |
02-02.txt |
RE |
49 ms |
1664 KB |
02-03.txt |
RE |
48 ms |
2944 KB |
02-04.txt |
AC |
61 ms |
4352 KB |
02-05.txt |
AC |
53 ms |
1920 KB |
02-06.txt |
RE |
61 ms |
4352 KB |
02-07.txt |
AC |
57 ms |
2048 KB |
02-08.txt |
RE |
39 ms |
1536 KB |
02-09.txt |
AC |
59 ms |
3964 KB |
02-10.txt |
AC |
51 ms |
3584 KB |
02-11.txt |
RE |
49 ms |
3584 KB |
02-12.txt |
AC |
50 ms |
3584 KB |
02-13.txt |
RE |
50 ms |
3456 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
RE |
1 ms |
256 KB |