제출 #368060

#제출 시각아이디문제언어결과실행 시간메모리
368060benedict0724Bosses (BOI16_bosses)C++17
67 / 100
1589 ms1008 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adj[5001]; queue<int> q; bool visited[5001]; int dp[5001]; int n; int dfs(vector<int> tree[5001], int x){ int sum = 0, ret = 0; for(int i : tree[x]){ ret += dfs(tree, i); sum += dp[i]; } dp[x] = sum + 1; return ret + dp[x]; } int bfs(int x){ for(int i=1;i<=n;i++) visited[i] = false; visited[x] = true; vector<int> tree[5001]; q.push(x); while(!q.empty()){ int now = q.front(); q.pop(); for(int i : adj[now]){ if(!visited[i]){ tree[now].push_back(i); visited[i] = true; q.push(i); } } } bool flag = false; for(int i=1;i<=n;i++){ if(!visited[i]) flag = true; } if(flag) return 1e9; else return dfs(tree, x); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i=1;i<=n;i++){ int k; cin >> k; for(int j=1;j<=k;j++){ int e; cin >> e; adj[e].push_back(i); } } int ans = 1e9; for(int i=1;i<=n;i++){ ans = min(ans, bfs(i)); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...