Submission #1275706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275706		behrad	Bosses (BOI16_bosses)	C++17	100 / 100	375 ms	728 KiB

bosses

#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, cnt = 0;
  while (q.size()) {
    int v = q.front(); q.pop();
    ++ cnt;
    res += dis[v];
    for (int u : adj[v]) {
      if (dis[u] == -1) {
        dis[u] = dis[v] + 1;
        q.push(u);
      }
    }
  }
  if (cnt == n) return res;
  else return n * (n + 1);
}

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;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33