Submission #1074776

#TimeUsernameProblemLanguageResultExecution timeMemory
1074776IcelastBosses (BOI16_bosses)C++17
67 / 100
1515 ms856 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int n; cin >> n; vector<int> a(n+1); vector<vector<int>> boss(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; for(int j = 1; j <= a[i]; j++){ int v; cin >> v; boss[i].push_back(v); } } vector<vector<int>> adj(n+1); vector<bool> latest(n+1, false); vector<bool> vis(n+1, false); vector<int> aval, left; vector<int> t; ll ans = INF; for(int root = 1; root <= n; root++){ ll res = 0; ll left = n-1; for(int i = 1; i <= n; i++){ latest[i] = false; vis[i] = false; } aval.clear(); aval.push_back(root); latest[root] = true; vis[root] = true; for(int d = 1; d <= n; d++){ if(aval.empty()) break; t.clear(); res += d*aval.size(); for(int i = 1; i <= n; i++){ if(vis[i]) continue; for(int j : boss[i]){ if(latest[j]){ t.push_back(i); break; } } } for(int i = 1; i <= n; i++) latest[i] = false; for(int i : t){latest[i] = true; left--; vis[i] = true;} aval = t; } if(left > 0) res = INF; ans = min(ans, res); } cout << ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...