Submission #7899530

---

Source Code Expand

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
template <typename T>
vector<T> dijkstra(int s,vector<vector<pair<int, T> > > & G){  
  const T INF = numeric_limits<T>::max();    
  using P = pair<T, int>;
  int n=G.size();
  vector<T> d(n,INF);
  vector<int> b(n,-1);
  priority_queue<P,vector<P>,greater<P> > q;
  d[s]=0;
  q.emplace(d[s],s);
  while(!q.empty()){
    P p=q.top();q.pop();
    int v=p.second;
    if(d[v]<p.first) continue;
    for(auto& e:G[v]){
      int u=e.first;
      T c=e.second;
      if(d[u]>d[v]+c){
        d[u]=d[v]+c;
        b[u]=v;
        q.emplace(d[u],u);
      }
    }
  }
  return d;
}
signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,m,k,l;
  string ans="YES";
  cin>>n>>m;
  priority_queue<int> pque;
  using P=pair<int,int>;
  vector<vector<P>> L(n+m);
  for(int i=0;i<n;i++){
    cin>>k;
    for(int j=0;j<k;j++){
      cin>>l;
      L[i].emplace_back(l+n-1,1);
      L[l+n-1].emplace_back(i,1);
    }
  }
  for(int i=1;i<n;i++){
    pque.push(dijkstra(0,L)[i]);
  }
  if(pque.top()==numeric_limits<int>::max()){ans="NO";}
  cout<<ans;
}

Submission Info

Judge Result