Submission #155948

#TimeUsernameProblemLanguageResultExecution timeMemory
155948aloo123Bosses (BOI16_bosses)C++14
100 / 100
1143 ms764 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define f first #define s second #define mp make_pair #define pb push_back #define vll vector<ll> #define fastio ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL) using namespace std; const ll N = 5005; const ll MOD = 1e9+7; vll adj[N]; vll adj2[N]; ll dp[N]; ll dis[N]; bool vis[N]; ll bfs(ll cur) { for(int i =0;i<N;i++) { dis[i]= -1; vis[i]=false; } queue<ll> q; q.push(cur); vis[cur]=true; dis[cur]=1; while(!q.empty()) { ll p = q.front(); q.pop(); for(auto v:adj[p]) { if(vis[v]==false) { vis[v]=true; dis[v]=dis[p]+1; q.push(v); } } } ll co =0; for(int i =1;i<N;i++) { if(vis[i]==false)continue; co+=dis[i]; } return co; } int main() { fastio; ll n; cin >> n; bool poss=true; ll src; for(int i =1;i<=n;i++) { ll k; cin >> k; if(k==0) { src=i; poss=false; } for(int j =1;j<=k;j++) { ll x; cin >> x; adj[x].pb(i); } } if(!poss) { ll sum=bfs(src); cout<<sum<<endl; return 0; } ll ans = LLONG_MAX; for(int i=1;i<=n;i++) { ll co=0; ll sum=bfs(i); for(int j =1;j<=n;j++) { if(vis[j])co++; } if(co==n) //cout << i << " " << dp[i] << endl; ans=min(ans,sum); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...