Submission #272883

#	Time	Username	Problem	Language	Result	Execution time	Memory
272883		toonewbie	Bosses (BOI16_bosses)	C++17	100 / 100	858 ms	760 KiB

bosses

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define endl '\n'
#define ll long long
#define pi pair<int,int>

using namespace std;

const int MOD = 1e9 + 7;
const int N = 5005;

int n;
vector<int> g[N];

int used[N], sz[N];
int get(int rt) {
    for (int i = 1; i <= n; i++) {
        used[i] = 0;
        sz[i] = -1;
    }
    queue<int> q; q.push(rt); used[rt] = 1; sz[rt] = 1;
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i : g[cur]) {
            if (used[i] == 0) {
                used[i] = 1;
                q.push(i);
                sz[i] = sz[cur] + 1;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (sz[i] == -1) return -1;
        res += sz[i];
    }
    return res;
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1, c, x; i <= n; i++) {
        cin >> c;
        while(c--) cin >> x, g[x].pb(i);
    }
    int res = MOD;
    for (int i = 1; i <= n; i++) {
        int cur = get(i);
        if (cur != -1) res = min(res, cur);
    }
    cout << res << endl;
    return 0;
}

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