제출 #1303538

#제출 시각아이디문제언어결과실행 시간메모리
1303538ffeyyaae_Bosses (BOI16_bosses)C++20
100 / 100
685 ms1016 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5005; int n; vector<int> child[N], adj[N]; bool vis[N]; int sal[N]; void dfs( int u ) { sal[u] = 1; for( auto v : adj[u] ) { dfs(v); sal[u] += sal[v]; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n; for( int i=1;i<=n;i++ ) { int k; cin >> k; for( int j=0;j<k;j++ ) { int a; cin >> a; child[a].push_back(i); } } int mn = 1e9; for( int i=1;i<=n;i++ ) { fill( vis+1, vis+n+1, false ); vis[i] = true; queue<int> q; q.push(i); while( !q.empty() ) { int node = q.front(); q.pop(); adj[node].clear(); for( int cur : child[node] ) { if( vis[cur] ) continue; vis[cur] = true; adj[node].push_back(cur); q.push(cur); } } bool chk = false; for( int j=1;j<=n;j++ ) { if( !vis[j] ) { chk = true; break; } } if( chk ) continue; dfs(i); int sum = 0; for( int j=1;j<=n;j++ ) sum += sal[j]; mn = min( mn, sum ); } cout << mn << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...