Submission #408828

#	Time	Username	Problem	Language	Result	Execution time	Memory
408828		danielcm585	Bosses (BOI16_bosses)	C++14	100 / 100	725 ms	648 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 5e3;
const int INF = 1e9;
int n;
int dis[N+2];
vector<int> lst[N+2];

int bfs(int st) {
    for (int i = 1; i <= n; i++) dis[i] = -1;
    queue<int> q;
    q.push(st); dis[st] = 0;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nx : lst[cur]) {
            if (dis[nx] != -1) continue;
            dis[nx] = dis[cur]+1;
            q.push(nx);
        }
    }
    int ret = n;
    for (int i = 1; i <= n; i++) {
        if (dis[i] == -1) return INF;
        ret += dis[i];
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            lst[x].push_back(i);
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans,bfs(i));
    }
    cout << ans << '\n';
    return 0;
}

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