Submission #695095

#	Time	Username	Problem	Language	Result	Execution time	Memory
695095		NeroZein	Bosses (BOI16_bosses)	C++17	100 / 100	611 ms	716 KiB

bosses

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

const int N = 5001;
vector<int> g[N];

int cnt;
long long tmp;
int cost[N];
inline void bfs(int v, int d = 1) {
  queue<int> q; 
  tmp = cnt = 0; 
  memset(cost, -1, sizeof cost);
  cost[v] = 1; 
  q.push(v);
  while(!q.empty()) {
    cnt++;
    int src = q.front();
    tmp += cost[src];
    q.pop();
    for (int u : g[src]) {
      if (cost[u] == -1) {
        cost[u] = cost[src] + 1; 
        q.push(u);
      }
    }
  }
}

signed main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int k;
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int x;
      cin >> x;
      g[x].push_back(i);
    }
  }
  long long ans = LLONG_MAX / 3; 
  for (int i = 1; i <= n; ++i) {
    bfs(i);
   if (cnt == n) {
      ans = min(ans, tmp);
   }
  }
  cout << ans << '\n';
}

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