oj.uz

답안 #79518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79518 2018-10-15T01:27:12 Z minhtung0404 Bosses (BOI16_bosses) C++17
100 / 100
 793 ms 1084 KB 
//https://oj.uz/problem/view/BOI16_bosses

#include<bits/stdc++.h>
const int N = 5005;
using namespace std;

vector <int> adj[N];
int n, d[N], ans = N*N;

void bfs(int u){
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i++) d[i] = 0;
    queue <int> mq;
    mq.push(u); d[u] = 1;
    while(mq.size()){
        int u = mq.front(); mq.pop();
        sum += d[u]; cnt++;
        for (auto v : adj[u]){
            if (!d[v]){
                d[v] = d[u] + 1;
                mq.push(v);
            }
        }
    }
    if (cnt == n) ans = min(ans, sum);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k, x; cin >> k;
        while (k--){
            cin >> x;
            adj[x].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) bfs(i);
    cout << ans;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 660 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 8 ms 748 KB Output is correct
13 Correct 5 ms 748 KB Output is correct
14 Correct 146 ms 844 KB Output is correct
15 Correct 17 ms 844 KB Output is correct
16 Correct 654 ms 876 KB Output is correct
17 Correct 793 ms 1004 KB Output is correct
18 Correct 782 ms 1084 KB Output is correct