# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
397164 |
2021-05-01T16:05:40 Z |
giorgikob |
Bosses (BOI16_bosses) |
C++14 |
|
844 ms |
24032 KB |
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N = 1e6+50, mod = 1e9+7, K = 31;
int n,k,x;
ll answer,res;
vector<int>gr[N];
bool fix[N];
int cnt = 0;
void bfs(int x){
queue<pair<int,int>>q;
q.push({x,1});
fix[x] = 1;
while(q.size()){
auto p = q.front();
q.pop();
int x = p.ff;
int h = p.ss;
cnt++;
res += h;
for(auto to : gr[x]){
if(fix[to]) continue;
q.push({to,h+1});
fix[to] = 1;
}
}
}
inline void test_case(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> k;
for(int j = 1; j <= k; j++){
cin >> x;
//v[i].pb(x);
gr[x].pb(i);
}
}
ll answer = 1e18;
for(int i = 1; i <= n; i++){
bfs(i);
if(cnt == n)answer = min(answer, res);
res = 0;
cnt = 0;
for(int j = 1; j <= n; j++) fix[j] = 0;
}
cout << answer << endl;
}
main(){
ios::sync_with_stdio(0);
int T = 1;
//cin >> T;
for(int i = 1; i <= T; i++){
test_case();
}
}
Compilation message
bosses.cpp:59:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
59 | main(){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23692 KB |
Output is correct |
2 |
Correct |
13 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23812 KB |
Output is correct |
4 |
Correct |
14 ms |
23808 KB |
Output is correct |
5 |
Correct |
14 ms |
23808 KB |
Output is correct |
6 |
Correct |
14 ms |
23756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23692 KB |
Output is correct |
2 |
Correct |
13 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23812 KB |
Output is correct |
4 |
Correct |
14 ms |
23808 KB |
Output is correct |
5 |
Correct |
14 ms |
23808 KB |
Output is correct |
6 |
Correct |
14 ms |
23756 KB |
Output is correct |
7 |
Correct |
14 ms |
23756 KB |
Output is correct |
8 |
Correct |
15 ms |
23756 KB |
Output is correct |
9 |
Correct |
13 ms |
23800 KB |
Output is correct |
10 |
Correct |
13 ms |
23740 KB |
Output is correct |
11 |
Correct |
14 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23692 KB |
Output is correct |
2 |
Correct |
13 ms |
23756 KB |
Output is correct |
3 |
Correct |
14 ms |
23812 KB |
Output is correct |
4 |
Correct |
14 ms |
23808 KB |
Output is correct |
5 |
Correct |
14 ms |
23808 KB |
Output is correct |
6 |
Correct |
14 ms |
23756 KB |
Output is correct |
7 |
Correct |
14 ms |
23756 KB |
Output is correct |
8 |
Correct |
15 ms |
23756 KB |
Output is correct |
9 |
Correct |
13 ms |
23800 KB |
Output is correct |
10 |
Correct |
13 ms |
23740 KB |
Output is correct |
11 |
Correct |
14 ms |
23884 KB |
Output is correct |
12 |
Correct |
18 ms |
23884 KB |
Output is correct |
13 |
Correct |
16 ms |
23860 KB |
Output is correct |
14 |
Correct |
198 ms |
23908 KB |
Output is correct |
15 |
Correct |
28 ms |
23816 KB |
Output is correct |
16 |
Correct |
667 ms |
24012 KB |
Output is correct |
17 |
Correct |
844 ms |
24012 KB |
Output is correct |
18 |
Correct |
836 ms |
24032 KB |
Output is correct |