# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
718154 |
2023-04-03T13:03:41 Z |
thimote75 |
Bosses (BOI16_bosses) |
C++14 |
|
621 ms |
740 KB |
#include <bits/stdc++.h>
using namespace std;
#define idata vector<int>
#define graph vector<idata>
#define INF 1e9
int nbNodes;
graph roads;
int bfs (int start) {
idata dist (nbNodes, INF);
queue<int> q;
dist[start] = 0;
q.push(start);
int res = 0;
int con = 0;
while (q.size() != 0) {
int curr = q.front();
q.pop();
res += dist[curr];
con ++;
for (int next : roads[curr]) {
if (dist[next] != INF) continue ;
dist[next] = dist[curr] + 1;
q.push(next);
}
}
if (con != nbNodes) return INF;
return res;
}
int answer () {
int res = INF;
for (int id = 0; id < nbNodes; id ++)
res = min(res, bfs(id));
return res + nbNodes;
}
int main () {
cin >> nbNodes;
roads.resize(nbNodes);
for (int id = 0; id < nbNodes; id ++) {
int cnt; cin >> cnt;
for (int jd = 0; jd < cnt; jd ++) {
int x;
cin >> x; x --;
roads[x].push_back(id);
}
}
cout << answer();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
296 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
296 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
296 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
6 ms |
364 KB |
Output is correct |
13 |
Correct |
5 ms |
340 KB |
Output is correct |
14 |
Correct |
124 ms |
436 KB |
Output is correct |
15 |
Correct |
20 ms |
552 KB |
Output is correct |
16 |
Correct |
490 ms |
740 KB |
Output is correct |
17 |
Correct |
619 ms |
636 KB |
Output is correct |
18 |
Correct |
621 ms |
692 KB |
Output is correct |