Submission #1342412

#TimeUsernameProblemLanguageResultExecution timeMemory
1342412inimadBosses (BOI16_bosses)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

#define LL long long
const int N = 5005;
vector<LL> g[N];
LL vis[N], sal[N];

void dfs(int u){
    vis[u] = 1;

    for(auto v : g[u]){
        if(vis[v] == 0){
            dfs(v);
            sal[u] += sal[v];
        }
    }
    sal[u]++;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    LL n;
    cin >> n;   
    for(int i = 1; i <= n; i++){
        LL k;
        cin >> k;
        while(k--){
            LL x; cin >> x;
            g[x].push_back(i);
        }
    }

    LL ans = 1e18;
    for(int i = 1; i <= n; i++){
        
        memset(sal, 0, sizeof sal);
        memset(vis, 0, sizeof vis);

        dfs(i);

        LL res = 0, ok = 0;
        for(int i = 1; i <= n; i++){
            if(sal[i] == 0){
                ok = 1;
                break;
            }
            res += sal[i];
        }

        if(ok != 1) ans = min(ans, res);
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...