Submission #235312

#	Time	Username	Problem	Language	Result	Execution time	Memory
235312		parsa_mobed	Bosses (BOI16_bosses)	C++14	100 / 100	730 ms	888 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
const int N = 5e3 + 5;
int dis[N], res, cnt, n, ans = 1e9;
vector <int> g[N];

void BFS(int v) {
    memset(dis, 31, sizeof dis), res = cnt = 0;
    queue <int> q;
    dis[v] = 0, q.push(v);
    while (!q.empty()) {
        v = q.front(), q.pop();
        res += dis[v] + 1, cnt++;
        for (int u : g[v]) if (dis[v] + 1 < dis[u]) dis[u] = dis[v] + 1, q.push(u);
    }
    if (cnt == n) ans = min(ans, res);
}

int main() {
  	ios::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 = 0; j < k; j++) {
            int u; cin >> u;
            g[u].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) BFS(i);
    cout << ans << "\n";

    return 0;
}

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