oj.uz

Submission #520688

# Submission time Handle Problem Language Result Execution time Memory
520688 2022-01-30T20:14:04 Z Alex_tz307 Bosses (BOI16_bosses) C++17
100 / 100
 1349 ms 1008 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int kN = 5e3;
vector<int> t[1 + kN];
int sum;

int dfs(int u) {
  int salary = 1;
  for (int v : t[u]) {
    salary += dfs(v);
  }
  sum += salary;
  return salary;
}

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

void testCase() {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  for (int v = 1; v <= n; ++v) {
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
      int u;
      cin >> u;
      g[u].emplace_back(v);
    }
  }
  int ans = INF;
  for (int root = 1; root <= n; ++root) {
    for (int v = 1; v <= n; ++v) {
      t[v].clear();
    }
    queue<int> q;
    q.emplace(root);
    vector<int> vis(n + 1);
    vis[root] = 1;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : g[u]) {
        if (!vis[v]) {
          t[u].emplace_back(v);
          q.emplace(v);
          vis[v] = 1;
        }
      }
    }
    sum = 0;
    dfs(root);
    if (accumulate(vis.begin(), vis.end(), 0) == n) {
      minSelf(ans, sum);
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 4 ms 572 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 316 ms 792 KB Output is correct
15 Correct 36 ms 764 KB Output is correct
16 Correct 1032 ms 1008 KB Output is correct
17 Correct 1349 ms 932 KB Output is correct
18 Correct 1308 ms 924 KB Output is correct