Submission #159457

#	Time	Username	Problem	Language	Result	Execution time	Memory
159457		a_player	Bosses (BOI16_bosses)	C++14	100 / 100	1088 ms	760 KiB

bosses

#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 i=0;i<grafo[co].size();i++){
        if(!v[grafo[co][i]]){
          val[grafo[co][i]]=val[co]+1;
          v[grafo[co][i]]=1;
          q.push(grafo[co][i]);
        }
      }
    }
    for(int i=0;i<N;i++)if(!v[i])return (int)1e9;
    return s;

}

int main(){
  cin>>N;
  for(int i=0;i<N;i++){
    int n;
    cin>>n;
    for(int j=0;j<n;j++){
      int a;
      cin>>a;
      grafo[a-1].push_back(i);
    }
  }
  int mini=bfs(0);
  for(int i=1;i<N;i++){
    mini=min(mini,bfs(i));
  }
  cout<<mini;
}

Compilation message (stderr)

bosses.cpp: In function 'int bfs(int)':
bosses.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<grafo[co].size();i++){
                   ~^~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33