Submission #1305191

#TimeUsernameProblemLanguageResultExecution timeMemory
1305191metaliusBosses (BOI16_bosses)C++20
100 / 100
800 ms792 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vii = vector<vi>; int n; int ans(int root, vii & adj) { vector<bool> used(n+1); vector<ll> dp(n+1); vector<int> par(n+1); stack<int> order; queue<int> q; q.push(root); used[root] = true; int vis = 0; while(!q.empty()) { int v = q.front(); q.pop(); used[v] = true; vis++; order.push(v); for(auto cld : adj[v]) { if(!used[cld]) { q.push(cld); used[cld] = true; par[cld] = v; } } } ll res = 0; if(vis != n) return INT32_MAX; // detect leaves while(!order.empty()) { int fr = order.top(); order.pop(); for(auto cld : adj[fr]) { if(par[cld] == fr) { dp[fr] += dp[cld]; } } dp[fr]++; res += dp[fr]; } return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; vii adj(n+1); for(int i = 1; i <= n;i++) { int k; cin >> k; for(int j = 0; j < k; j++) { int a; cin >> a; adj[a].push_back(i); } } int res = INT32_MAX; for(int i = 1; i <= n;i++) { res = min(res,ans(i,adj)); } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...