oj.uz

답안 #701004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701004 2023-02-19T17:18:29 Z Behradm Bosses (BOI16_bosses) C++17
100 / 100
 1257 ms 960 KB 
//In The Name Of GOD
#include "bits/stdc++.h"

#define sz(x) ((int) (x).size())

using namespace std;
using LL = long long;

const int N = 5e3 + 5;
vector<int> out[N], g[N];
int sz[N];

void dfs(int u) {
  sz[u] = 1;
  for (int v : g[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int u;
      cin >> u, --u;
      out[u].push_back(i);
    }
  }

  long long ans = 3e18;
  for (int u = 0; u < n; u++) {
    for (int i = 0; i < n; i++)
      g[i].clear();
    vector<bool> mk(n, 0);
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      mk[v] = 1;
      for (int w : out[v]) {
        if (!mk[w]) {
          mk[w] = 1;
          q.push(w);
          g[v].push_back(w);
        }
      }
    }

    memset(sz, 0, sizeof sz);
    dfs(u);
    long long res = 0;
    bool ok = 1;
    for (int i = 0; i < n; i++) {
      res += sz[i];
      ok &= sz[i] >= 1;
    }
    if (ok)
      ans = min(ans, res);
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 6 ms 736 KB Output is correct
13 Correct 4 ms 720 KB Output is correct
14 Correct 328 ms 872 KB Output is correct
15 Correct 44 ms 764 KB Output is correct
16 Correct 966 ms 892 KB Output is correct
17 Correct 1232 ms 960 KB Output is correct
18 Correct 1257 ms 948 KB Output is correct