oj.uz

답안 #79525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79525 2018-10-15T01:49:08 Z EntityIT Bosses (BOI16_bosses) C++14
100 / 100
 627 ms 936 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = 5e3 + 5;
int n, ans = 1e9, cur, h[N];
vector<int> gr[N];

void bfs (int u) {
    queue<int> q; q.push(u); h[u] = 1;
    while (!q.empty() ) {
        u = q.front(); q.pop();
        for (int v : gr[u]) if (!h[v]) {
            h[v] = h[u] + 1;
            q.push(v);
        }
        cur += h[u];
    }
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int u = 1; u <= n; ++u) {
        int K; cin >> K;
        while (K --) {
            int v; cin >> v;
            gr[v].pb(u);
        }
    }

    for (int u = 1; u <= n; ++u) {
        bfs(u);
        bool ok = 1;
        for (int v = 1; v <= n; ++v) if (!h[v]) ok = 0;
        if (ok) ans = min(ans, cur);
        cur = 0;
        memset(h, 0, sizeof h);
    }

    cout << ans;

    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 2 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 752 KB Output is correct
12 Correct 6 ms 752 KB Output is correct
13 Correct 5 ms 764 KB Output is correct
14 Correct 133 ms 856 KB Output is correct
15 Correct 21 ms 856 KB Output is correct
16 Correct 627 ms 920 KB Output is correct
17 Correct 613 ms 936 KB Output is correct
18 Correct 626 ms 936 KB Output is correct