Submission #79525

#	Time	Username	Problem	Language	Result	Execution time	Memory
79525		EntityIT	Bosses (BOI16_bosses)	C++14	100 / 100	627 ms	936 KiB

bosses

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = 5e3 + 5;
int n, ans = 1e9, cur, h[N];
vector<int> gr[N];

void bfs (int u) {
    queue<int> q; q.push(u); h[u] = 1;
    while (!q.empty() ) {
        u = q.front(); q.pop();
        for (int v : gr[u]) if (!h[v]) {
            h[v] = h[u] + 1;
            q.push(v);
        }
        cur += h[u];
    }
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int u = 1; u <= n; ++u) {
        int K; cin >> K;
        while (K --) {
            int v; cin >> v;
            gr[v].pb(u);
        }
    }

    for (int u = 1; u <= n; ++u) {
        bfs(u);
        bool ok = 1;
        for (int v = 1; v <= n; ++v) if (!h[v]) ok = 0;
        if (ok) ans = min(ans, cur);
        cur = 0;
        memset(h, 0, sizeof h);
    }

    cout << ans;

    return 0;
}

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