Submission #533526

#TimeUsernameProblemLanguageResultExecution timeMemory
533526devariaotaBosses (BOI16_bosses)C++17
100 / 100
779 ms764 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll N,M;
bool visited[5005];
vector <ll> adj[5005];
int main(){
  cin>>N;
  for(int i=1;i<=N;i++){
    cin>>M;
    for(int j=1;j<=M;j++){
      ll temp;
      cin>>temp;
      adj[temp].push_back(i);
    }
  }
  ll minn=1e18;
  for(int i=1;i<=N;i++){
    memset(visited,false,sizeof(visited));
    queue <pair<ll,ll> > que;
    que.push({i,1});
    visited[i]=true;
    ll catat=1;
    ll sum=1;
    while(!que.empty()){
      ll x=que.front().fi;
      ll val=que.front().se;
      que.pop();
      for(auto j:adj[x]){
        if(!visited[j]){
          visited[j]=true;
          catat++;
          sum+=val+1;
          que.push({j,val+1});
        }
      }
    }
    if(catat==N){
      minn=min(minn,sum);
    }
  }
  cout<<minn<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...