Submission #779758

#TimeUsernameProblemLanguageResultExecution timeMemory
779758Sandarach151Bosses (BOI16_bosses)C++17
22 / 100
1 ms212 KiB
#include<bits/stdc++.h> using namespace std; vector<vector<long long>> adg; vector<vector<long long>> adgtree; void dfs(long long cur, long long salary[]){ if(adgtree[cur].empty()){ salary[cur]= 1; } else{ long long cnt = 0; for(auto next : adgtree[cur]){ dfs(next, salary); cnt+=salary[next]; } salary[cur]=cnt+1; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long n; cin >> n; adg.resize(n); for(long long i=0; i<n; i++){ long long a; cin >> a; for(long long j=0; j<a; j++){ long long b; cin >> b; adg[b-1].push_back(i); } } long long ans = -1; for(long long root = 0; root<n; root++){ bool vsted[n] = {false}; adgtree.clear(); adgtree.resize(n); queue<int> que; que.push(root); vsted[root]=true; while(!que.empty()){ long long cur = que.front(); que.pop(); for(auto u : adg[cur]){ if(!vsted[u]){ vsted[u]=true; adgtree[cur].push_back(u); que.push(u); } } } long long salary[n]; dfs(root, salary); long long curans = 0; for(long long i=0; i<n; i++){ curans+=salary[i]; } if(ans==(long long) -1){ ans = curans; } else{ ans = min(ans, curans); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...