Submission #651936

#	Time	Username	Problem	Language	Result	Execution time	Memory
651936		pauloamed	Bosses (BOI16_bosses)	C++14	100 / 100	880 ms	98924 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5010;
vector<int> v[MAXN];

int d[MAXN][MAXN];

int main(){
  memset(d, -1, sizeof d);

  cin.tie(NULL)->sync_with_stdio(false);
  int n; cin >> n;
  for(int i = 0; i < n; ++i){
    int k; cin >> k;
    for(int j = 0; j < k; ++j){
      int y; cin >> y; y--;
      v[y].push_back(i);
    }

  }

  // for(int i = 0; i < n; ++i){
  //   cout << i << ": ";
  //   for(auto x : v[i]) cout << x << " ";
  //   cout << endl;
  // }

  int ans = INT_MAX;
  for(int i = 0; i < n; ++i){
    queue<int> q;
    q.push(i);
    d[i][i] = 1;
    while(q.size()){
      int x = q.front(); q.pop();
      for(auto y : v[x]) if(d[i][y] == -1){
        q.push(y);
        d[i][y] = d[i][x] + 1;
      }
    }

    int sum = 0;

    // cout << i << ":\n";
    for(int j = 0; j < n; ++j){
      // cout << d[i][j] << " ";
      if(d[i][j] == -1){
        sum = INT_MAX; break;
      }else sum += d[i][j];
    }
    // cout << "\n";
    ans = min(ans, sum);
  }
  cout << ans << "\n";
}

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