Submission #1167282

#TimeUsernameProblemLanguageResultExecution timeMemory
1167282ocasuBosses (BOI16_bosses)C++20
100 / 100
609 ms820 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int inf=5e18; signed main(){ int n; cin>>n; vector<vector<int>> adj(n+1); for (int i=1; i<=n; i++){ int k; cin>>k; for (int j=0; j<k; j++){ int x; cin>>x; adj[x].push_back(i); } } int ans=inf; for (int r=1; r<=n; r++){ vector<int> d(n+1,-1); vector<int> numInLayer(n+1,0); queue<pair<int,int>> q; q.push({r,0}); int numVis=0; while (!q.empty()){ auto [node,dist]=q.front(); q.pop(); if (d[node]!=-1) continue; d[node]=dist; numInLayer[dist]++; numVis++; for (auto i: adj[node]) q.push({i,dist+1}); } if (numVis<n) continue; int sum=0; for (int i=n-1; i>=0; i--) { numInLayer[i] += numInLayer[i+1]; //cout<<"L "<<i<<' '<<numInLayer[i]<<'\n'; sum+=numInLayer[i]; } //cout<<"X "<<r<<' '<<sum<<'\n'; ans=min(ans, sum); } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...