Submission #79514

#	Time	Username	Problem	Language	Result	Execution time	Memory
79514		atoiz	Bosses (BOI16_bosses)	C++14	100 / 100	680 ms	1176 KiB

bosses

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

using namespace std;

const int MAX = 5007;
const int INF = 1e8;
int n;
vector<int> gr[MAX];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int v = 1; v <= n; ++v) {
        int k, u; cin >> k;
        for (int j = 0; j < k; ++j) {
            cin >> u; gr[u].push_back(v);
        }
    }

    int ans = INF;
    for (int root = 1; root <= n; ++root) {
        vector<int> hei(n + 1, INF);
        hei[root] = 0;
		queue<int> qu;
		qu.push(root);
        while (!qu.empty()) {
			int u = qu.front(); qu.pop();
            for (int v : gr[u]) {
                if (hei[v] < INF) continue;
                hei[v] = hei[u] + 1;
                qu.push(v);
            }
        }

        int curAns = n;
        bool full = 1;
        for (int u = 1; u <= n && full; ++u) {
            if (hei[u] == INF) full = 0;
			else curAns += hei[u];
        }
        if (full) ans = min(ans, curAns);
    }
    cout << ans;
}

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