제출 #676102

#제출 시각아이디문제언어결과실행 시간메모리
676102sudheerays123Bosses (BOI16_bosses)C++17
0 / 100
1 ms468 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> adj[N]; vector<ll> ssize(N) , parent(N); void dfs(ll s , ll p){ ssize[s] = 1; for(auto u : adj[s]){ if(parent[u] != s) continue; dfs(u,s); ssize[s] += ssize[u]; } } void solve(){ ll n; cin >> n; for(ll i = 1; i <= n; i++){ ll x; cin >> x; while(x--){ ll a; cin >> a; adj[a].push_back(i); } } ll ans = INF; for(ll root = 1; root <= n; root++){ vector<ll> depth(n+5,-1); parent[root] = 0; depth[root] = 1; queue<ll> q; q.push(root); while(q.size()){ ll a = q.front(); q.pop(); for(auto u : adj[a]){ if(depth[u] == -1){ depth[u] = depth[a]+1; parent[u] = a; q.push(u); } } } ll cost = 0; dfs(root,0); 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...