oj.uz

Submission #256997

# Submission time Handle Problem Language Result Execution time Memory
256997 2020-08-03T13:46:16 Z rama_pang Bosses (BOI16_bosses) C++14
100 / 100
 875 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N;
  cin >> N;
  vector<vector<int>> adj(N);
  for (int i = 0; i < N; i++) {
    int k;
    cin >> k;
    while (k--) {
      int a;
      cin >> a;
      a--;
      adj[a].emplace_back(i);
    }
  }

  auto Solve = [&](int s) -> long long {
    vector<int> dist(N, -1);
    queue<int> q;
    q.emplace(s);
    dist[s] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : adj[u]) {
        if (dist[v] == -1) {
          dist[v] = dist[u] + 1;
          q.emplace(v);
        }
      }
    }
    if (count(begin(dist), end(dist), -1) > 0) {
      return 1e18;
    }
    long long ans = 0;
    for (int i = 0; i < N; i++) {
      ans += dist[i] + 1;
    }
    return ans;
  };

  long long ans = 1e18;
  for (int i = 0; i < N; i++) {
    ans = min(ans, Solve(i));
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 174 ms 760 KB Output is correct
15 Correct 37 ms 640 KB Output is correct
16 Correct 623 ms 760 KB Output is correct
17 Correct 875 ms 760 KB Output is correct
18 Correct 811 ms 736 KB Output is correct