Submission #1342040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342040		inimad	Bosses (BOI16_bosses)	C++20	0 / 100	0 ms	344 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

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

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++){
        LL mx = 0;

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

        while(!q.empty()){
            LL 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;
                }
            }
        }
    
        LL res = 0, ok = 0;
        for(int i = 1; i <= n; i++){
            if(vis[i] == 0){
                ok = 1;
                break;
            }
            res += mx - lvl[i] + 1; 
        }

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

    cout << ans;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33