Submission #700999

#TimeUsernameProblemLanguageResultExecution timeMemory
700999BehradmBosses (BOI16_bosses)C++17
0 / 100
1 ms340 KiB
//In The Name Of GOD
#include "bits/stdc++.h"

#define sz(x) ((int) (x).size())

using namespace std;
using LL = long long;

const int N = 5e3 + 5;
vector<int> out[N];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int u;
      cin >> u, --u;
      out[u].push_back(i);
    }
  }

  long long ans = 3e18;
  for (int u = 0; u < n; u++) {
    vector<int> d(n, -1);
    queue<int> q;
    q.push(u);
    d[u] = 0;
    while (!q.empty()) {
      int v = q.front(); q.pop();
      for (int w : out[v]) {
        if (d[w] == -1) {
          d[w] = d[v] + 1;
          q.push(w);
        }
      }
    }

    long long res = n;
    for (int i = 0; i < n; i++)
      res += d[i];
    ans = min(ans, res);
  }
  cout << ans << '\n';
  return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...