oj.uz

Submission #1014633

# Submission time Handle Problem Language Result Execution time Memory
1014633 2024-07-05T08:34:17 Z t_holl Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 348 KB 
#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 == 0) 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();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -