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
AC × 1
RE × 1
AC × 8
RE × 4
AC × 16
RE × 11
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