제출 #676113

#제출 시각아이디문제언어결과실행 시간메모리
676113sudheerays123Bosses (BOI16_bosses)C++17
0 / 100
2 ms596 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int const ll N = 5000+5 , INF = 1e18 , MOD = 1e9+7; vector<ll> ssize(N); vector<ll> adj2[N]; void dfs(ll s){ ssize[s] = 1; for(auto u : adj2[s]){ dfs(u); ssize[s] += ssize[u]; } } void solve(){ ll n; cin >> n; vector<ll> adj1[N]; for(ll i = 1; i <= n; i++){ ll x; cin >> x; while(x--){ ll a; cin >> a; adj1[a].push_back(i); } } ll ans = INF; for(ll root = 1; root <= n; root++){ vector<ll> depth(n+5,-1); for(ll i = 1; i <= n; i++) adj2[i].clear(); depth[root] = 1; queue<ll> q; q.push(root); while(q.size()){ ll a = q.front(); q.pop(); for(auto u : adj1[a]){ if(depth[u] == -1){ depth[u] = depth[a]+1; q.push(u); adj2[a].push_back(u); } } } ll cost = 0; dfs(root); for(ll i = 1; i <= n; i++) cost += ssize[i]; ans = min(ans,cost); } cout << ans; } int main(){ fast; ll tc = 1; // cin >> tc; while(tc--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...