oj.uz

답안 #239231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239231 2020-06-14T21:19:29 Z aggu_01000101 Bosses (BOI16_bosses) C++14
100 / 100
 820 ms 728 KB 
#include <bits/stdc++.h>
#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<int> children[n];
    for(int i =0 ;i<n;i++){
        int k;
        cin>>k;
        while(k--){
            int par;
            cin>>par;
            children[par-1].push_back(i);
        }
    }
    int ans = INF;
    for(int i = 0;i<n;i++){
        bool chosen[n];
        for(int j = 0;j<n;j++) chosen[j] = false;
        chosen[i] = true;
        queue<pair<int, int>> q;
        q.push({i, 0});
        int cnt = 1;
        int cost = 0;
        while(!q.empty()){
            pair<int, int> curr = q.front();
            cost+=(curr.second + 1);
            q.pop();
            for(int j: children[curr.first]){
                if(chosen[j]) continue;
                cnt++;
                chosen[j] = true;
                q.push({j, curr.second+1});
            }
        }
        if(cnt!=n) continue;
        ans = min(ans, cost);
    }
    cout<<ans<<"\n";
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 8 ms 512 KB Output is correct
13 Correct 7 ms 512 KB Output is correct
14 Correct 176 ms 640 KB Output is correct
15 Correct 17 ms 640 KB Output is correct
16 Correct 604 ms 640 KB Output is correct
17 Correct 820 ms 728 KB Output is correct
18 Correct 805 ms 640 KB Output is correct