Submission #1014636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014636		t_holl	Bosses (BOI16_bosses)	C++14	100 / 100	549 ms	872 KiB

bosses

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

igrid roads;
idata bfs_states; int i_state = 0;
idata distances;

int bfs (int start) {
    i_state ++;

    int cnt = 1;
    queue<int> q; q.push(start);
    bfs_states[start] = i_state;
    distances [start] = 0;

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

        for (int next : roads[curr]) {
            if (bfs_states[next] == i_state) continue ;

            bfs_states[next] = i_state;
            distances [next] = distances[curr] + 1;
            q.push(next);
            cnt ++;
        }
    }

    if (cnt != roads.size()) return 1e18;

    int res = 0;
    for (int u : distances) res += u + 1;
    return res;
}

void solve () {
    int N;
    cin >> N;

    roads     .resize(N);
    distances .resize(N);
    bfs_states.resize(N);

    for (int i = 0; i < N; i ++) {
        int k; cin >> k;
        for (int j = 0; j < k; j ++) {
            int n; cin >> n;
            roads[n - 1].push_back(i);
        }
    }

    int res = 1e18;
    for (int i = 0; i < N; i ++) res = min(res, bfs(i));

    cout << res << "\n";
}

signed main () {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

Compilation message (stderr)

bosses.cpp: In function 'long long int bfs(long long int)':
bosses.cpp:38:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     if (cnt != roads.size()) return 1e18;
      |         ~~~~^~~~~~~~~~~~~~~

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