oj.uz

답안 #877510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877510 2023-11-23T09:29:57 Z Beerus13 Bosses (BOI16_bosses) C++14
100 / 100
 408 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e3 + 5;

int n;
vector<int> g[N];
int dp[N];

int bfs(int u) {
    queue<int> q;
    memset(dp, 0, sizeof(dp));
    dp[u] = 1;
    q.push(u);
    while(q.size()) {
        int s = q.front(); q.pop();
        for(int t : g[s]) if(dp[t] == 0) {
            dp[t] = dp[s] + 1;
            q.push(t);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        res += dp[i];
        if(dp[i] == 0) return 1e9;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int k, x; cin >> k;
        while(k--) {
            cin >> x;
            g[x].push_back(i);
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= n; ++i) ans = min(ans, bfs(i));
    cout << ans << '\n';
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 592 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 592 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 692 KB Output is correct
14 Correct 70 ms 600 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 401 ms 704 KB Output is correct
17 Correct 398 ms 600 KB Output is correct
18 Correct 408 ms 852 KB Output is correct