Submission #159552

#	Time	Username	Problem	Language	Result	Execution time	Memory
159552		InfiniteJest	Bosses (BOI16_bosses)	C++14	100 / 100	1161 ms	952 KiB

bosses

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <map>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
typedef long long ll;
 
int fi(){
  char g=getchar_unlocked();
  while(g<'0'||g>'9')g=getchar_unlocked();
  int num=0;
  while(g>='0'&&g<='9'){
    num=(num<<1)+(num<<3)+g-48;
    g=getchar_unlocked();
  }
  return num;
}
 
int n;
vector<int> nodi[5001];
vector<int> p[5001];
bool vis[5001];
int minn=1e9;
int val[5001];
int f;
int sum=0;
 
void bfs(int k){
  queue<pair<int,int> > q;
  q.push(mp(k,1));
  vis[k]=1;
  while(!q.empty()){
    int cur=q.front().fi;
    f++;
    int depth=q.front().se;
    sum+=q.front().se;
    q.pop();
    for(int i=0;i<nodi[cur].size();i++){
      if(vis[nodi[cur][i]])continue;
      vis[nodi[cur][i]]=1;
      q.push(mp(nodi[cur][i],depth+1));
    }
  }
}
 
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  n=fi();
  for(int i=0;i<n;i++){
    int k; k=fi();
    for(int y=0;y<k;y++){
      int a; a=fi();
      nodi[a-1].pb(i);
    }
  }
  for(int i=0;i<n;i++){
    for(int y=0;y<n;y++){
      p[y].clear();
      vis[y]=0;
      val[y]=0;
    }
    f=0;
    sum=0;
    bfs(i);
    if(f!=n)continue;
    minn=min(minn,sum);
    //cout<<"i "<<i<<" v "<<sum<<endl;
  }
  cout<<minn;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<nodi[cur].size();i++){
                 ~^~~~~~~~~~~~~~~~~

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