oj.uz

Submission #329589

# Submission time Handle Problem Language Result Execution time Memory
329589 2020-11-21T18:17:19 Z gustason Bosses (BOI16_bosses) C++14
100 / 100
 971 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxN = 5005;
const int INF = 1e9 + 5;
int n;
vector<int> adj[maxN];
vector<bool> visited(maxN);

int bfs(int root) {
    for(int i = 0; i <= n; i++) {
        visited[i] = false;
    }

    queue<pair<int, int>> q;
    q.push({root, 1});
    visited[root] = true;

    ll cost = 0;
    while(!q.empty()) {
        auto v = q.front();
        q.pop();
        cost += v.second;

        for(int u : adj[v.first]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push({u, v.second+1});
            }
        }
    }

    if (count(visited.begin(), visited.end(), true) != n) return INF;
    return cost;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int ord = 1; ord <= n; ord++) {
        int k;
        cin >> k;
        for(int j = 0; j < k; j++) {
            int boss;
            cin >> boss;
            adj[boss].push_back(ord);
        }
    }


    int best = INF;
    // root the tree at every possible vertex
    for(int boss = 1; boss <= n; boss++) {
        best = min(best, bfs(boss));
    }

    cout << best;
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 7 ms 512 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 268 ms 620 KB Output is correct
15 Correct 88 ms 492 KB Output is correct
16 Correct 754 ms 664 KB Output is correct
17 Correct 876 ms 620 KB Output is correct
18 Correct 971 ms 748 KB Output is correct