Submission #734833

#	Time	Username	Problem	Language	Result	Execution time	Memory
734833		dong_liu	Bosses (BOI16_bosses)	C++17	100 / 100	596 ms	672 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5000;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(NULL);
  int n; cin >> n;
  static vector<int> c[N];
  for (int i = 0; i < n; i++) {
    int k; cin >> k;
    while (k--) {
      int j; cin >> j, j--;
      c[j].push_back(i);
    }
  }
  long long ans = LLONG_MAX;
  for (int s = 0; s < n; s++) {
    static int d[N];
    memset(d, -1, n * 4);
    queue<int> q;
    d[s] = 0, q.push(s);
    while (!q.empty()) {
      int i = q.front(); q.pop();
      for (int j : c[i]) if (d[j] == -1)
        d[j] = d[i] + 1, q.push(j);
    }
    long long x = 0; bool f = 0;
    for (int i = 0; i < n; i++)
      if (d[i] == -1) { f = 1; break; }
      else x += d[i] + 1;
    if (!f) ans = min(ans, x);
  }
  cout << ans << '\n';
}

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