Submission #891630

#	Time	Username	Problem	Language	Result	Execution time	Memory
891630		ind1v	Bosses (BOI16_bosses)	C++11	100 / 100	412 ms	796 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;

int n;
vector<int> g[N];
bool vis[N];
int lv[N];
int ans = 1e9;

void bfs(int u) {
  memset(lv, -1, sizeof(lv));
  lv[u] = 1;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int nxt : g[v]) {
      if (lv[nxt] == -1) {
        lv[nxt] = lv[v] + 1;
        q.push(nxt);
      }
    }
  }
  if (*min_element(lv + 1, lv + n + 1) > -1) {
    ans = min(ans, accumulate(lv + 1, lv + n + 1, 0));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int k;
    cin >> k;
    for (int j = 1; j <= k; j++) {
      int x;
      cin >> x;
      g[x].emplace_back(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    bfs(i);
  }
  cout << ans << '\n';
  return 0;
}

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