oj.uz

Submission #35328

# Submission time Handle Problem Language Result Execution time Memory
35328 2017-11-20T08:47:59 Z nickyrio Bosses (BOI16_bosses) C++14
100 / 100
 719 ms 2328 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 5050
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
#define bit(S, i) (((S) >> i) & 1)
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

int n, k, u, p[N];
vector<int> e[N];
queue<int> q;
long long d[N];

long long bfs(int s) {
    FOR(i, 1, n) p[i] = 0;
    p[s] = -1;
    d[s] = 1;
    q.push(s);
    int cnt = 0;
    long long ans = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans += d[u];
        cnt++;
        for (int v : e[u]) if (p[v] == 0) {
            p[v] = u;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    if (cnt == n) return ans;
    return 1e18;
}
int main() {
    IO;
    read(n);
    FOR(i, 1, n) {
        read(k);
        while (k--) {
            read(u);
            e[u].push_back(i);
        }
    }
    long long ans = 1e18;
    FOR(i, 1, n) ans = min(ans, bfs(i));
    writeln(ans);
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2196 KB Output is correct
2 Correct 0 ms 2196 KB Output is correct
3 Correct 0 ms 2196 KB Output is correct
4 Correct 0 ms 2196 KB Output is correct
5 Correct 0 ms 2196 KB Output is correct
6 Correct 0 ms 2196 KB Output is correct
7 Correct 0 ms 2196 KB Output is correct
8 Correct 0 ms 2196 KB Output is correct
9 Correct 0 ms 2196 KB Output is correct
10 Correct 0 ms 2196 KB Output is correct
11 Correct 0 ms 2196 KB Output is correct
12 Correct 3 ms 2328 KB Output is correct
13 Correct 0 ms 2328 KB Output is correct
14 Correct 153 ms 2328 KB Output is correct
15 Correct 16 ms 2328 KB Output is correct
16 Correct 716 ms 2328 KB Output is correct
17 Correct 716 ms 2328 KB Output is correct
18 Correct 719 ms 2328 KB Output is correct