Submission #1346327

#TimeUsernameProblemLanguageResultExecution timeMemory
1346327nathlol2Bosses (BOI16_bosses)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, ans = INT_MAX, cnt, vis[N];
vector<int> adj[N];

int dfs(int u){
    int res = 1;
    vector<int> g;
    for(auto v : adj[u]){
        if(!vis[v]) g.push_back(v), vis[v] = 1;
    }
    for(auto v : g){
        res += dfs(v);
    }
    cnt += res;
    return res;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++){
        int k; cin >> k;
        for(int j = 0;j<k;j++){
            int u; cin >> u;
            adj[u].push_back(i);
        }
    }
    for(int i = 1;i<=n;i++){
        memset(vis, 0, sizeof vis);
        cnt = 0;
        vis[i] = 1;
        dfs(i);
        bool ok = 1;
        for(int j = 1;j<=n;j++) ok &= vis[j];
        if(ok) ans = min(ans, cnt);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...