oj.uz

Submission #606948

# Submission time Handle Problem Language Result Execution time Memory
606948 2022-07-26T10:26:48 Z jjiangly Bosses (BOI16_bosses) C++14
100 / 100
 819 ms 648 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf LLONG_MAX

const int nxm = int(5e3) + 7;
int n, k, u;
vt<vt<int>> e(nxm);

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> k;
    for (int j = 0; j < k; ++j) {
      cin >> u;
      --u;
      e[u].push_back(i);
    }
  }
  int ans = inf;
  for (int i = 0; i < n; ++i) {
    //vt<vt<int>> e2(nxm);
    int cnt = 0;
    int tot = 0;
    function<void()> bfs = [&]() {
      vt<bool> vis(n, false);
      queue<ar<int, 2>> que;
      que.push({i, 1});
      while (que.size()) {
        u = que.front()[0];
        int p = que.front()[1];
        que.pop();
        if (vis[u]) {
          continue;
        }
        tot += p;
        ++cnt;
        //if (p != -1) {
          //e2[p].push_back(u);
        //}
        vis[u] = true;
        for (int v : e[u]) {
          if (!vis[v]) {
            que.push({v, p + 1});
          }
        }
      }
    };
    bfs();
    if (cnt != n) {
      continue;
    }
    //vt<int> d(n, 0);
    //function<void(int)> dfs = [&](int root) {
      //int sum = 0;
      //for (int v : e2[root]) {
        //dfs(v);
        //sum += d[v];
      //}
      //d[root] = sum + 1;
      //tot += d[root];
    //};
    //dfs(i);
    ans = min(ans, tot);
  }
  cout << ans << "\n";

  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 17 ms 548 KB Output is correct
13 Correct 13 ms 468 KB Output is correct
14 Correct 153 ms 496 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 649 ms 588 KB Output is correct
17 Correct 819 ms 648 KB Output is correct
18 Correct 742 ms 648 KB Output is correct