Submission #256870

#TimeUsernameProblemLanguageResultExecution timeMemory
256870NightlightBosses (BOI16_bosses)C++14
100 / 100
997 ms908 KiB
#include <bits/stdc++.h> #define pii pair<int, int> using namespace std; int N, K; vector<int> adj[5005]; bool ok[5005]; int topo[5005], par[5005], pos[5005]; int p; long long sz[5005]; long long ans = LLONG_MAX; void solve(int rt) { p = N - 1; queue<pii> q; memset(ok, 0, sizeof(ok)); ok[rt] = 1; for(int v : adj[rt]) q.emplace(v, rt); topo[N] = rt; par[rt] = 0; int u; while(!q.empty()) { u = q.front().first; if(ok[u] == 0) { ok[u] = 1; topo[p] = u, pos[u] = p; par[u] = q.front().second; for(int v : adj[u]) { q.emplace(v, u); } p--; } q.pop(); } if(p) return; memset(sz, 0, sizeof(sz)); long long res = 0; // cout << rt << ":\n"; for(int i = 1; i <= N; i++) { u = topo[i]; // cout << u << " " << par[u] << "\n"; sz[u]++; res += sz[u]; sz[par[u]] += sz[u]; } ans = min(ans, res); } int main() { ios_base::sync_with_stdio(0); cin >> N; int u; for(int i = 1; i <= N; i++) { cin >> K; while(K--) { cin >> u; adj[u].emplace_back(i); } } for(int i = 1; i <= N; i++) solve(i); cout << ans << "\n"; cin >> N; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...