Submission #1342028

#TimeUsernameProblemLanguageResultExecution timeMemory
1342028inimadBosses (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<int> g[N];
int vis[N], lvl[N];

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

    int ans = 1e9;
    for(int i = 1; i <= n; i++){
        int mx = 0;

        memset(vis, 0, sizeof vis);
        memset(lvl, 0, sizeof lvl);
        
        queue<int> q;
        q.push(i);
        lvl[i] = vis[i] = 1;

        while(!q.empty()){
            int k = q.front();
            mx = max(mx, lvl[k]);
            q.pop();

            for(auto v : g[k]){
                if(vis[v] == 0){
                    lvl[v] = lvl[k] + 1;
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(vis[i] == 0) break;
            res += mx - lvl[i] + 1; 
        }

        if(res != 0) ans = min(ans, res);
    }

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