Submission #1275703

#TimeUsernameProblemLanguageResultExecution timeMemory
1275703behradBosses (BOI16_bosses)C++17
0 / 100
1 ms572 KiB
#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 5005, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, dis[maxn];
vector<int> adj[maxn];

inline int bfs(int s) {
  fill(dis, dis + n + 1, -1);
  queue<int> q;
  dis[s] = 1;
  q.push(s);
  int res = 0;
  while (q.size()) {
    int v = q.front(); q.pop();
    res += dis[v];
    for (int u : adj[v]) {
      if (dis[u] == -1) {
        dis[u] = dis[v] + 1;
        q.push(u);
      }
    }
  }
  return res;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n;
  for (int i = 1 , k, x ; i <= n ; i ++) {
    cin >> k;
    while (k --) {
      cin >> x;
      adj[x].pb(i);
    }
  }

  int ans = n * (n + 1);
  for (int i = 1 ; i <= n ; i ++) {
    ans = min(ans, bfs(i));
  }
  cout << ans << nl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...