oj.uz

Submission #234000

# Submission time Handle Problem Language Result Execution time Memory
234000 2020-05-22T17:11:37 Z DS007 Bosses (BOI16_bosses) C++14
100 / 100
 764 ms 888 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5000;
vector<int> adj[N];
bool explored[N];
int dist[N];
int n, c;

int solveTestCase(int test) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int k, v;
        cin >> k;
        while (k--) {
            cin >> v;
            adj[v - 1].push_back(i);
        }
    }

    int ans = 1e18;
    for (int i = 0; i < n; i++) {
        fill(dist, dist + N, 1e18);
        fill(explored, explored + N, false);
        int val = 1;
        dist[i] = 1;
        explored[i] = true;

        queue<int> q;
        q.push(i);
        c = 1;

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int j : adj[v]) {
                if (!explored[j])
                    dist[j] = dist[v] + 1, val += dist[j], q.push(j), explored[j] = true, c++;
            }
        }

        if (c == n)
            ans = min(ans, val);
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message

bosses.cpp: In function 'long long int solveTestCase(long long int)':
bosses.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 168 ms 640 KB Output is correct
15 Correct 31 ms 760 KB Output is correct
16 Correct 597 ms 760 KB Output is correct
17 Correct 756 ms 764 KB Output is correct
18 Correct 764 ms 888 KB Output is correct