oj.uz

Submission #888208

# Submission time Handle Problem Language Result Execution time Memory
888208 2023-12-16T11:25:55 Z Danet Bosses (BOI16_bosses) C++14
100 / 100
 503 ms 848 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 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 580 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 580 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 156 ms 672 KB Output is correct
15 Correct 56 ms 672 KB Output is correct
16 Correct 465 ms 756 KB Output is correct
17 Correct 503 ms 848 KB Output is correct
18 Correct 461 ms 772 KB Output is correct