Submission #159458

#TimeUsernameProblemLanguageResultExecution timeMemory
159458a_playerBosses (BOI16_bosses)C++14
100 / 100
1012 ms676 KiB
#include <bits/stdc++.h>

using namespace std;

vector<int> grafo[5001];
int val[5001];
int v[5001];
queue<int> q;
int N;
int fast(){
  int r=0;
  char ch=getchar();
  while(ch<'0' or ch>'9')ch=getchar();
  r=ch-'0';
  ch=getchar();
  while(ch>='0'&&ch<='9'){
    r=(r<<1)+(r<<3)+ch-'0';
    ch=getchar();
  }
  return r;
}

int bfs(int in){
    memset(v,0,sizeof(v));
    memset(val,0,sizeof(val));
    int s=0;
    q.push(in);
    v[in]=1;
    val[in]=1;
    while(!q.empty()){
      int co=q.front();
      q.pop();
      s+=val[co];
      for(int x:grafo[co]){
        if(!v[x]){
          val[x]=val[co]+1;
          v[x]=1;
          q.push(x);
        }
      }
    }
    for(int i=0;i<N;i++)if(!v[i])return (int)1e9;
    return s;

}

int main(){
  N=fast();
  for(int i=0;i<N;i++){
    int n;
    n=fast();
    for(int j=0;j<n;j++){
      int a;
      a=fast();
      grafo[a-1].push_back(i);
    }
  }
  int mini=bfs(0);
  for(int i=1;i<N;i++){
    mini=min(mini,bfs(i));
  }
  cout<<mini;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...