제출 #220481

#제출 시각아이디문제언어결과실행 시간메모리
220481CalicoBosses (BOI16_bosses)C++17
67 / 100
1595 ms1016 KiB
#include <bits/stdc++.h> using namespace std; int n, ans = 100000000; vector<short> adj[5001]; vector<short> adj_tr[5001]; short dp[5001], 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(); } memset(dp, 0, sizeof(dp)); memset(dist, 0, sizeof(dist)); memset(prv, 0, sizeof(prv)); memset(vis, 0, sizeof(vis)); 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--) { short 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...