제출 #373922

#제출 시각아이디문제언어결과실행 시간메모리
373922Aryan_RainaBosses (BOI16_bosses)C++14
67 / 100
1594 ms1132 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; int n; ar<int,2> dfs(int u, vector<int> g[]) { int ans = 0, cur = 1; for (int v : g[u]) { ar<int,2> tmp = dfs(v, g); ans += tmp[1]; cur += tmp[0]; } return {cur, ans + cur}; } int bfs(int rt, vector<int> g[]) { vector<bool> vis(n, 0); queue<int> q; vector<int> children[n]; q.push(rt); vis[rt] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (!vis[v]) { children[u].push_back(v); vis[v] = 1; q.push(v); } } for (int i = 0; i < n; i++) if (!vis[i]) return INF; return dfs(rt, children)[1]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; vector<int> g[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, g)); cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...