Submission #888928

#	Time	Username	Problem	Language	Result	Execution time	Memory
888928		Perl32	Bosses (BOI16_bosses)	C++14	100 / 100	412 ms	808 KiB

bosses

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const ll INF = (ll) 1e18 + 1e9;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int par;
            cin >> par;
            g[par - 1].push_back(i);
        }
    }
    auto Bfs = [&](int u) -> ll {
        vector<ll> dist(n, INF);
        queue<int> que;
        dist[u] = 1;
        que.push(u);
        ll ret = 0;
        int used = 0;
        while (!que.empty()) {
            int v = que.front();
            ret += dist[v];
            used++;
            que.pop();
            for (auto to : g[v]) {
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    que.push(to);
                }
            }
        }
        if (used != n) {
            return INF;
        }
        return ret;
    };
    ll mn = INF;
    for (int i = 0; i < n; ++i) {
        mn = min(mn, Bfs(i));
    }
    cout << mn;
}

/*

 */

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