Submission #680235

#	Time	Username	Problem	Language	Result	Execution time	Memory
680235		Tigerpants	Bosses (BOI16_bosses)	C++17	100 / 100	854 ms	700 KiB

bosses

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

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;

const ll INF = 5000 * 10000;

vvll g;
ll n;

vb vis;
ll solve(ll cur) {
    vll h(n, 1);
    queue<ll> bfs;
    fill_n(vis.begin(), n, false);
    vis[cur] = true;
    ll ans = 0;
    bfs.push(cur);

    while (!bfs.empty()) {
        ll next = bfs.front();
        bfs.pop();
        ans += h[next];

        for (vll::iterator child = g[next].begin(); child != g[next].end(); child++) {
            if (!vis[*child]) {
                vis[*child] = true;
                bfs.push(*child);
                h[*child] = h[next] + 1;
            }
        }
    }

    bool verify = true;
    for (int i = 0; i < n; i++) {verify &= vis[i];}

    if (verify) {return ans;} return INF;
}

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

    cin >> n;
    g.resize(n);
    ll k_tmp;
    ll inp_tmp;
    for (int i = 0; i < n; i++) {
        cin >> k_tmp;
        for (int j = 0; j < k_tmp; j++) {
            cin >> inp_tmp;
            g[inp_tmp - 1].push_back(i);
        }
    }

    ll min_sum = INF;
    vis.resize(n);
    for (int i = 0; i < n; i++) {
        fill_n(vis.begin(), n, false);
        min_sum = min<ll>(min_sum, solve(i));
    }

    cout << min_sum << endl;

    return 0;
}

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