제출 #306349

#제출 시각아이디문제언어결과실행 시간메모리
306349kaplanbarBosses (BOI16_bosses)C++14
0 / 100
1 ms384 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int N = 5e3+5; int n; vector<int> adj[N]; int solve(int root) { vector<int> val(n, 0), from(n, -1); vector<bool> vis(n); queue<int> q; q.push(root); vis[root] = 1; stack<int> s; while(!q.empty()) { int now = q.front(); q.pop(); s.push(now); for(int v : adj[now]) { if(vis[v]) continue; from[v] = now; vis[v] = 1; q.push(v); } } for(int i = 0; i < n; i++) { if(!vis[i]) return 1e9; } while(!s.empty()) { int now = s.top(); s.pop(); val[now]++; if(from[now] != -1) { val[from[now]] += val[now]; } } int ret = 0; for(int i = 0; i < n; i++) ret += val[i]; return ret; } int main() { ios_base::sync_with_stdio(false); cin >> n; for(int i = 0; i < n; i++) { int x; cin >> x; for(int j = 0; j < x; j++) { int t; cin >> t; t--; adj[t].push_back(i); } } int ans = 1e9; for(int i = 0; i < n; i++) { ans = min(ans, solve(i)); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...