oj.uz

Submission #857759

# Submission time Handle Problem Language Result Execution time Memory
857759 2023-10-06T21:45:32 Z qrno Bosses (BOI16_bosses) C++17
100 / 100
 548 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) begin(v), end(v)

int N;
vector<vector<int>> G;

int bfs(int v) {
  vector<int> val(N, -1);
  queue<pair<int, int>> Q;
  val[v] = 1;
  Q.push({v, val[v]});

  while (!Q.empty()) {
    auto [v, x] = Q.front(); Q.pop();
    for (auto u : G[v]) {
      if (val[u] == -1) {
        val[u] = x+1;
        Q.push({u, val[u]});
      }
    }
  }

  if (*min_element(all(val)) == -1) return -1;
  return accumulate(all(val), 0LL);
}

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

  cin >> N;
  G.resize(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;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 448 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 448 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 564 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 142 ms 728 KB Output is correct
15 Correct 27 ms 600 KB Output is correct
16 Correct 537 ms 860 KB Output is correct
17 Correct 548 ms 820 KB Output is correct
18 Correct 526 ms 816 KB Output is correct