Submission #390054

#	Time	Username	Problem	Language	Result	Execution time	Memory
390054		BThero	Bosses (BOI16_bosses)	C++17	100 / 100	1424 ms	952 KiB

bosses

// chrono::system_clock::now().time_since_epoch().count()
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = (int)5e3 + 5;
const int INF = (int)1e9;

vi g[MAXN], adj[MAXN];
int d[MAXN];
int n;

pair<ll, ll> dfs(int v) {
    pair<ll, ll> ret = mp(0, 0);

    for (int to : g[v]) {
        pair<ll, ll> cur = dfs(to);
        ret.fi += cur.fi;
        ret.se += cur.se;
    }

    ret.fi++;
    ret.se += ret.fi;
    return ret;
}

void solve() {
    cin >> n;

    rep (i, 1, n + 1) {
        int k;
        cin >> k;

        rep (j, 0, k) {
            int x;
            cin >> x;
            adj[x].pb(i);
        }
    }

    queue<int> q;
    ll ans = (ll)1e18;

    rep (i, 1, n + 1) {
        fill(d + 1, d + n + 1, INF);
        fill(g + 1, g + n + 1, vi());
        d[i] = 0;
        q.push(i);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int to : adj[v]) {
                if (d[to] == INF) {
                    d[to] = d[v] + 1;
                    g[v].pb(to);
                    q.push(to);
                }
            }
        }

        if (*max_element(d + 1, d + n + 1) != INF) {
            ans = min(ans, dfs(i).se);
        }
    } 

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;

    for (int i = 1; i <= tt; ++i) {
        solve();
    }

    return 0;
}

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