# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
651936 |
2022-10-20T15:16:37 Z |
pauloamed |
Bosses (BOI16_bosses) |
C++14 |
|
880 ms |
98924 KB |
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
vector<int> v[MAXN];
int d[MAXN][MAXN];
int main(){
memset(d, -1, sizeof d);
cin.tie(NULL)->sync_with_stdio(false);
int n; cin >> n;
for(int i = 0; i < n; ++i){
int k; cin >> k;
for(int j = 0; j < k; ++j){
int y; cin >> y; y--;
v[y].push_back(i);
}
}
// for(int i = 0; i < n; ++i){
// cout << i << ": ";
// for(auto x : v[i]) cout << x << " ";
// cout << endl;
// }
int ans = INT_MAX;
for(int i = 0; i < n; ++i){
queue<int> q;
q.push(i);
d[i][i] = 1;
while(q.size()){
int x = q.front(); q.pop();
for(auto y : v[x]) if(d[i][y] == -1){
q.push(y);
d[i][y] = d[i][x] + 1;
}
}
int sum = 0;
// cout << i << ":\n";
for(int j = 0; j < n; ++j){
// cout << d[i][j] << " ";
if(d[i][j] == -1){
sum = INT_MAX; break;
}else sum += d[i][j];
}
// cout << "\n";
ans = min(ans, sum);
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
98636 KB |
Output is correct |
2 |
Correct |
39 ms |
98596 KB |
Output is correct |
3 |
Correct |
36 ms |
98648 KB |
Output is correct |
4 |
Correct |
38 ms |
98636 KB |
Output is correct |
5 |
Correct |
38 ms |
98656 KB |
Output is correct |
6 |
Correct |
37 ms |
98536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
98636 KB |
Output is correct |
2 |
Correct |
39 ms |
98596 KB |
Output is correct |
3 |
Correct |
36 ms |
98648 KB |
Output is correct |
4 |
Correct |
38 ms |
98636 KB |
Output is correct |
5 |
Correct |
38 ms |
98656 KB |
Output is correct |
6 |
Correct |
37 ms |
98536 KB |
Output is correct |
7 |
Correct |
38 ms |
98544 KB |
Output is correct |
8 |
Correct |
37 ms |
98636 KB |
Output is correct |
9 |
Correct |
38 ms |
98624 KB |
Output is correct |
10 |
Correct |
38 ms |
98680 KB |
Output is correct |
11 |
Correct |
37 ms |
98692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
98636 KB |
Output is correct |
2 |
Correct |
39 ms |
98596 KB |
Output is correct |
3 |
Correct |
36 ms |
98648 KB |
Output is correct |
4 |
Correct |
38 ms |
98636 KB |
Output is correct |
5 |
Correct |
38 ms |
98656 KB |
Output is correct |
6 |
Correct |
37 ms |
98536 KB |
Output is correct |
7 |
Correct |
38 ms |
98544 KB |
Output is correct |
8 |
Correct |
37 ms |
98636 KB |
Output is correct |
9 |
Correct |
38 ms |
98624 KB |
Output is correct |
10 |
Correct |
38 ms |
98680 KB |
Output is correct |
11 |
Correct |
37 ms |
98692 KB |
Output is correct |
12 |
Correct |
40 ms |
98764 KB |
Output is correct |
13 |
Correct |
41 ms |
98688 KB |
Output is correct |
14 |
Correct |
176 ms |
98804 KB |
Output is correct |
15 |
Correct |
42 ms |
98744 KB |
Output is correct |
16 |
Correct |
586 ms |
98860 KB |
Output is correct |
17 |
Correct |
777 ms |
98924 KB |
Output is correct |
18 |
Correct |
880 ms |
98880 KB |
Output is correct |