oj.uz

답안 #340189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340189 2020-12-27T09:16:59 Z blue Bosses (BOI16_bosses) C++11
100 / 100
 958 ms 620 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
    S[i] = sum{j in children[i], S[j]} + 1

    => S[leaf] = 0

    Every non-leaf i contributes depth[i] to the total sum by increasing each of its ancestors and itself by 1

    So, answer = sum{i not a leaf, depth[i]}
    Do a BFS to find minimum depths. Try out every vertex as root once.
*/

int main()
{
    int n;
    cin >> n;

    vector<int> next[n+1];

    int a, b;
    for(int i = 1; i <= n; i++)
    {
        cin >> a;
        for(int j = 1; j <= a; j++)
        {
            cin >> b;
            next[b].push_back(i);
        }
    }

    int res = 2000000000, r;

    vector<int> S(n+1);
    queue<int> tbv, dist;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++) S[j] = 0;
        S[i] = 1;
        r = 1;
        tbv.push(i);
        dist.push(1);
        while(!tbv.empty())
        {
            for(int j:next[tbv.front()])
            {
                if(S[j]) continue;
                S[j] = dist.front() + 1;
                r += dist.front() + 1;
                dist.push(dist.front() + 1);
                tbv.push(j);
            }
            tbv.pop();
            dist.pop();
        }
        for(b = 1; b <= n; b++) if(S[b] == 0) break;
        if(b <= n) continue;
        res = min(res, r);
    }
    cout << res << '\n';
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 6 ms 364 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 191 ms 620 KB Output is correct
15 Correct 16 ms 620 KB Output is correct
16 Correct 723 ms 620 KB Output is correct
17 Correct 943 ms 620 KB Output is correct
18 Correct 958 ms 620 KB Output is correct