Submission #1288863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288863		harryleee	Bosses (BOI16_bosses)	C++20	100 / 100	352 ms	736 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 5010;
const int INF = 1e9;

int n, d[N], num, x;
bool vis[N];
vector <int> v[N];

int calc(int i) {
    fill_n(vis + 1, n, false);
    d[i] = 1;

    queue <int> q;
    q.push(i);
    vis[i] = true;

    int sum = 0, cnt = 0;
    while (!q.empty()) {
        int p = q.front(); q.pop();
        ++cnt;
        sum += d[p];

        for (int z: v[p]) {
            if (vis[z]) continue;
            vis[z] = true;
            d[z] = d[p] + 1;
            q.push(z);
        }
    }

    if (cnt < n) return INF;

    return sum;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> num;
        while (num--) {
            cin >> x;
            v[x].push_back(i);
        }
    }

    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, calc(i));
    }

    cout << ans << "\n";

    return 0;
}

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