Submission #701004

#TimeUsernameProblemLanguageResultExecution timeMemory
701004BehradmBosses (BOI16_bosses)C++17
100 / 100
1257 ms960 KiB
//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;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...