Submission #986474

#TimeUsernameProblemLanguageResultExecution timeMemory
986474ShaShiBosses (BOI16_bosses)C++17
100 / 100
436 ms25484 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define F first #define S second #define kill(x) cout << x << endl, exit(0); #define endl "\n" using namespace std; typedef long long ll; typedef long double ld; const int MAXN = (int)1e6 + 7; const int MOD = 998244853; const ll INF = (ll)1e18 + 7; int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M; int arr[MAXN], h[MAXN]; bool seen[MAXN]; vector<int> adj[MAXN]; queue<int> Q; void BFS(int v) { fill(seen, seen+n+1, 0); tmp = 0; Q.push(v); h[v] = seen[v] = 1; while (Q.size()) { v = Q.front(); Q.pop(); // cout << "@" << v << " " << h[v] << endl; tmp += h[v]; for (int u:adj[v]) { if (!seen[u]) { seen[u] = 1; h[u] = h[v]+1; Q.push(u); } } } for (int i=1; i<=n; i++) if (!seen[i]) return; ans = min(ans, tmp); } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i=1; i<=n; i++) { cin >> k; for (int j=1; j<=k; j++) { cin >> u; adj[u].pb(i); } } ans = INF; for (int i=1; i<=n; i++) BFS(i); cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...