oj.uz

Submission #79529

# Submission time Handle Problem Language Result Execution time Memory
79529 2018-10-15T01:51:06 Z FutymyClone Bosses (BOI16_bosses) C++14
100 / 100
 700 ms 1020 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;

vector <int> g[N];
bool visited[N];
int val[N], n, ans = 1e9;

void bfs (int s) {
    queue <int> q; q.push(s); visited[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v: g[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
                val[v] = val[u] + 1;
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int num; scanf("%d", &num);
        for (int j = 0; j < num; j++) {
            int v; scanf("%d", &v);
            g[v].push_back(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        memset(visited, 0, sizeof(visited));
        val[i] = 1;
        bool f = true;

        bfs(i);

        for (int j = 1; j <= n; j++) {
            if (!visited[j]) {
                f = false;
                break;
            }
        }

        if (!f) continue;

        int sum = 0;
        for (int j = 1; j <= n; j++) sum += val[j];
        ans = min(ans, sum);
    }

    printf("%d", ans);
    return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
bosses.cpp:28:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int num; scanf("%d", &num);
                  ~~~~~^~~~~~~~~~~~
bosses.cpp:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int v; scanf("%d", &v);
                    ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 584 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 8 ms 736 KB Output is correct
13 Correct 6 ms 736 KB Output is correct
14 Correct 128 ms 816 KB Output is correct
15 Correct 6 ms 816 KB Output is correct
16 Correct 606 ms 896 KB Output is correct
17 Correct 665 ms 924 KB Output is correct
18 Correct 700 ms 1020 KB Output is correct