제출 #220477

#제출 시각아이디문제언어결과실행 시간메모리
220477CalicoBosses (BOI16_bosses)C++17
67 / 100
1589 ms896 KiB
#include <bits/stdc++.h> using namespace std; int n, ans = 1000000000; vector<int> adj[5001]; vector<int> adj_tr[5001]; vector<int> dp(5001); vector<int> dist(5001), prv(5001), vis(5001); void dfs(int now) { int s = 0; for (int u: adj_tr[now]) { dfs(u); s += dp[u]; } dp[now] = s+1; } int bfs(int fi) { for (int i = 1; i <= n; i++) { adj_tr[i].clear(); dp[i] = 0; prv[i] = 0; dist[i] = 0; vis[i] = 0; } queue<int> q; q.push(fi); dist[fi] = 1; while (q.size()) { int now = q.front(); q.pop(); if (vis[now]) continue; vis[now] = 1; for (int u: adj[now]) { if (dist[u] == 0) { dist[u] = dist[now] + 1; q.push(u); prv[u] = now; } } } for (int i = 1; i <= n; i++) { if (i != fi) { if (prv[i] == 0) return ans; adj_tr[prv[i]].push_back(i); } } dfs(fi); int rs = 0; for (int i = 1; i <= n; i++) { rs += dp[i]; } return rs; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { int k; cin >> k; while (k--) { int x; cin >> x; adj[x].push_back(i); } } for (int i = 1; i <= n; i++) { ans = min(ans, bfs(i)); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...