Submission #139783

#	Time	Username	Problem	Language	Result	Execution time	Memory
139783		meatrow	Bosses (BOI16_bosses)	C++17	100 / 100	993 ms	736 KiB

bosses

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int mod = 1e9 + 7;
const int N = 5e3 + 1;

vector<int> kids[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int a;
            cin >> a;
            kids[a].push_back(i);
        }
    }
    int ans = INT32_MAX;
    for (int i = 1; i <= n; i++) {
        int sum = 1;
        vector<int> h(n + 1);
        h[i] = 1;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int u : kids[v]) {
                if (!h[u]) {
                    sum += (h[u] = h[v] + 1);
                    q.push(u);
                }
            }
        }
        if (*min_element(h.begin() + 1, h.end())) {
            ans = min(ans, sum);
        }
    }
    cout << ans;
    return 0;
}

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