Submission #373923

#TimeUsernameProblemLanguageResultExecution timeMemory
373923Aryan_RainaBosses (BOI16_bosses)C++14
67 / 100
1585 ms1004 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define ar array const int INF = 1e15; const int MOD = 1e9+7; const int MXN = 5005; vector<int> g[MXN]; int n; int bfs(int rt) { vector<bool> vis(n, 0); queue<int> q; vector<int> ch[n]; q.push(rt); vis[rt] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (!vis[v]) { ch[u].push_back(v); vis[v] = 1; q.push(v); } } int ans = 0; function<int(int)> dfs = [&](int u) { int cur = 1; for (int v : ch[u]) { cur += dfs(v); } ans += cur; return cur; }; dfs(rt); for (int i = 0; i < n; i++) if (!vis[i]) return INF; return ans; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for (int i = 0; i < n; i++) { int x; cin>>x; while (x--) { int j; cin>>j; --j; g[j].push_back(i); } } int ans = INF; for (int i = 0; i < n; i++) ans = min(ans, bfs(i)); cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...