Submission #230567

#	Time	Username	Problem	Language	Result	Execution time	Memory
230567		AlexLuchianov	Bosses (BOI16_bosses)	C++14	100 / 100	759 ms	768 KiB

bosses

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <queue>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 5000;
vector<int> g[1 + nmax];
int dist[1 + nmax];

int eval(int node, int n){
  for(int i = 1; i <= n; i++)
    dist[i] = 0;
  queue<int> q;

  dist[node] = 1;
  ll result = 0;
  q.push(node);
  while(0 < q.size()){
    int node = q.front();
    q.pop();
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(dist[to] == 0){
        dist[to] = dist[node] + 1;
        q.push(to);
      }
    }
  }

  for(int i = 1;i <= n; i++) {
    result += dist[i];
    if(0 == dist[i])
      return -1;
  }
  return result;
}
int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++){
    int k;
    cin >> k;
    for(int j = 1;j <= k; j++){
      int val;
      cin >> val;
      g[val].push_back(i);
    }
  }
  ll result = -1;
  for(int i = 1;i <= n; i++){
    int cost = eval(i, n);
    if(cost == -1)
      continue;
    if(result == -1)
      result = cost;
    else if(cost < result)
      result = cost;
  }
  cout << result;
  return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int eval(int, int)':
bosses.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~

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