Submission #329760

#TimeUsernameProblemLanguageResultExecution timeMemory
329760SuhaibSawalha1Bosses (BOI16_bosses)C++17
0 / 100
1 ms364 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> adj; int vid = 1; vector<int> visited, dp; void dfs (int u){ visited[u] = vid; dp[u] = 1; for (int v : adj[u]){ if (visited[v] ^ vid){ dfs(v); dp[u] += dp[v]; } } } int main (){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; adj.resize(n); for (int u = 0; u < n; ++u){ int k, v; cin >> k; while (k--){ cin >> v; adj[--v].push_back(u); } } visited.resize(n); dp.resize(n); long long ans = 1e18; for (int i = 0; i < n; ++i, ++vid){ dfs(i); ans = min(ans, all_of(visited.begin(), visited.end(), [] (int x) {return x == vid;}) ? accumulate(dp.begin(), dp.end(), 0ll) : (long long) 1e18); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...