#include <iostream>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;
int n;
vector<int> adj[5005], order, par, sz;
queue<int> bfs;
bitset<5005> vis;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int sz, i = 1; i <= n; i ++){
cin >> sz;
for(int p, j = 1; j <= sz; j ++){
cin >> p;
adj[p].push_back(i);
}
}
par.resize(n + 1);
int ans = 1e9 + 69;
for(int i = 1; i <= n; i ++){ //let i be the boss
vis = 0; order.clear();
bfs.push(i); vis[i] = 1;
for(; !bfs.empty(); bfs.pop()){
int nw = bfs.front();
order.push_back(nw);
for(int nx : adj[nw]) if(!vis[nx]){
vis[nx] = 1; bfs.push(nx);
par[nx] = nw;
}
}
if(order.size() != n) continue;
reverse(order.begin(), order.end());
int tmp = 0;
sz.assign(n + 1, 0);
for(int nw : order){
sz[nw] ++; tmp += sz[nw];
if(nw != i)
sz[par[nw]] += sz[nw];
}
ans = min(ans, tmp);
}
cout << ans << endl;
return 0;
}
Compilation message
bosses.cpp: In function 'int main()':
bosses.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(order.size() != n) continue;
~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
0 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
512 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
0 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
640 KB |
Output is correct |
14 |
Correct |
182 ms |
692 KB |
Output is correct |
15 |
Correct |
3 ms |
640 KB |
Output is correct |
16 |
Correct |
679 ms |
776 KB |
Output is correct |
17 |
Correct |
1168 ms |
892 KB |
Output is correct |
18 |
Correct |
1197 ms |
768 KB |
Output is correct |