Submission #718154

#	Time	Username	Problem	Language	Result	Execution time	Memory
718154		thimote75	Bosses (BOI16_bosses)	C++14	100 / 100	621 ms	740 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>
#define graph vector<idata>
#define INF 1e9

int nbNodes;
graph roads;

int bfs (int start) {
    idata dist (nbNodes, INF);

    queue<int> q;
    dist[start] = 0;
    q.push(start);

    int res = 0;
    int con = 0;

    while (q.size() != 0) {
        int curr = q.front();
        q.pop();

        res += dist[curr];
        con ++;

        for (int next : roads[curr]) {
            if (dist[next] != INF) continue ;

            dist[next] = dist[curr] + 1;
            q.push(next);
        }
    }

    if (con != nbNodes) return INF;
    return res;
}
int answer () {
    int res = INF;
    for (int id = 0; id < nbNodes; id ++)
        res = min(res, bfs(id));
    return res + nbNodes;
}

int main () {
    cin >> nbNodes;
    roads.resize(nbNodes);

    for (int id = 0; id < nbNodes; id ++) {
        int cnt; cin >> cnt;

        for (int jd = 0; jd < cnt; jd ++) {
            int x;
            cin >> x; x --;

            roads[x].push_back(id);
        }
    }

    cout << answer();
}

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