Submission #857762

#TimeUsernameProblemLanguageResultExecution timeMemory
857762qrnoBosses (BOI16_bosses)C++17
100 / 100
400 ms748 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e3;

int N;
array<vector<int>, MAXN> G;
array<int, MAXN> val, last;

int bfs(int src) {
  fill(begin(val), end(val), -1);

  queue<int> Q;
  val[src] = 1;
  last[src] = src;
  Q.push(src);

  int done = 0;
  int total = 0;
  while (!Q.empty()) {
    auto v = Q.front(); Q.pop();
    total += val[v];
    done++;
    for (auto u : G[v]) {
      if (last[u] != src) {
        val[u] = val[v]+1;
        last[u] = src;
        Q.push(u);
      }
    }
  }

  if (done < N) return -1;
  return total;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> N;
  for (int i = 0; i < N; i++) {
    int K; cin >> K;
    while (K--) {
      int u; cin >> u; u--;
      G[u].push_back(i);
    }
  }

  int best = -1;
  for (int i = 0; i < N; i++) {
    int sum = bfs(i);
    if (sum == -1) continue;
    if (best == -1 || best > sum)
      best = sum;
  }
  cout << best << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...