제출 #1275703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275703		behrad	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	572 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;
  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;
}

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