Submission #582311

#	Time	Username	Problem	Language	Result	Execution time	Memory
582311		stevancv	Bosses (BOI16_bosses)	C++14	100 / 100	634 ms	716 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        int sz; cin >> sz;
        while (sz--) {
            int x; cin >> x;
            x -= 1;
            g[x].push_back(i);
        }
    }
    ll ans = 1e9;
    for (int i = 0; i < n; i++) {
        queue<int> q;
        vector<int> d(n, 1e9);
        d[i] = 0;
        q.push(i);
        while (!q.empty()) {
            int s = q.front();
            q.pop();
            for (int u : g[s]) {
                if (d[u] > d[s] + 1) {
                    d[u] = d[s] + 1;
                    q.push(u);
                }
            }
        }
        ll tr = n;
        for (int j = 0; j < n; j++) tr += d[j];
        smin(ans, tr);
    }
    cout << ans << en;
    return 0;
}

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