제출 #724750

#제출 시각아이디문제언어결과실행 시간메모리
724750sofija6Bosses (BOI16_bosses)C++14
100 / 100
1332 ms992 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 5010 using namespace std; vector<ll> G[MAXN],cur[MAXN]; bool V[MAXN]; ll subtree[MAXN],sum; void DFS(ll i) { subtree[i]=1; for (ll next : cur[i]) { DFS(next); subtree[i]+=subtree[next]; } sum+=subtree[i]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,k,a,ans=LLONG_MAX; cin >> n; for (ll i=1;i<=n;i++) { cin >> k; for (ll j=1;j<=k;j++) { cin >> a; G[a].push_back(i); } } for (ll i=1;i<=n;i++) { for (ll j=1;j<=n;j++) { V[j]=false; cur[j].clear(); subtree[j]=0; sum=0; } queue<ll> q; q.push(i); V[i]=true; while (!q.empty()) { ll t=q.front(); for (ll next : G[t]) { if (!V[next]) { V[next]=true; cur[t].push_back(next); q.push(next); } } q.pop(); } DFS(i); if (subtree[i]==n) ans=min(ans,sum); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...