# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
340189 |
2020-12-27T09:16:59 Z |
blue |
Bosses (BOI16_bosses) |
C++11 |
|
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;
}
# |
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 |
# |
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 |
# |
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 |