oj.uz

Submission #340189

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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