Submission #1176235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176235		bangan	Bosses (BOI16_bosses)	C++20	100 / 100	391 ms	736 KiB

bosses

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> kid(n);
    for (int i = 0; i < n; i++) {
        int k;
        std::cin >> k;

        while (k--) {
            int f;
            std::cin >> f;
            kid[f - 1].push_back(i);
        }
    }

    i64 ans = 1LL * n * n + 1;
    auto test = [&](int r) {
        std::vector<int> dep(n, n + 1);
        dep[r] = 1;

        std::queue<int> q;
        q.push(r);

        i64 sum = 0LL;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            sum += dep[v];

            for (int u : kid[v]) {
                if (dep[u] == n + 1) {
                    dep[u] = dep[v] + 1;
                    q.push(u);
                }
            }
        }
    
        if (std::count(dep.begin(), dep.end(), n + 1) == 0) {
            ans = std::min(ans, sum);
        }
    };

    for (int i = 0; i < n; i++) {
        test(i);
    }
    std::cout << ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // int t;
    // std::cin >> t;

    // while (t--) {
    solve();
    // }

    return 0;
}

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