제출 #704733

#제출 시각아이디문제언어결과실행 시간메모리
704733speedyArdaBosses (BOI16_bosses)C++14
100 / 100
1310 ms980 KiB
#include "bits/stdc++.h" using namespace std; const int MAXN = 5005; vector< vector<int> > adj(MAXN), rev(MAXN); int main() { int n; cin >> n; for(int i = 1; i <= n; i++) { int amount; cin >> amount; while(amount--) { int f; cin >> f; adj[i].push_back(f); rev[f].push_back(i); } } queue<int> q; long long res = 1e18; for(int i = 1; i <= n; i++) { vector<bool> visited(n+5); vector<int> indeg(n+5); vector<long long> ans(n+5); vector<int> par(n+5, 1e9); visited[i] = true; par[i] = -1; queue<int> q; q.push(i); while(!q.empty()) { int v = q.front(); q.pop(); for(int e : rev[v]) { if(visited[e]) continue; visited[e] = true; par[e] = v; indeg[v]++; q.push(e); } } for(int idx = 1; idx <= n; idx++) { if(indeg[idx] == 0) q.push(idx); } long long temp = 0; while(!q.empty()) { int v = q.front(); q.pop(); ans[v]++; temp += ans[v]; if(par[v] != -1 && par[v] != 1e9) { indeg[par[v]]--; ans[par[v]] += ans[v]; if(indeg[par[v]] == 0) q.push(par[v]); } } for(int i = 1; i <= n; i++) { if(par[i] == 1e9) // There is an element which isn't in the hierarchy temp = 1e18; } res = min(res, temp); } cout << res << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...