# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
498460 |
2021-12-25T08:26:02 Z |
dsyz |
Bosses (BOI16_bosses) |
C++17 |
|
733 ms |
716 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
ll N;
cin>>N;
vector<ll> v[N];
for(ll i = 0;i < N;i++){
ll k;
cin>>k;
for(ll j = 0;j < k;j++){
ll a;
cin>>a;
a--;
v[a].push_back(i);
}
}
ll sum = 1000000000000005;
queue<ll> q;
ll dist[N];
int visited[N];
for(ll i = 0;i < N;i++){
memset(dist,0,sizeof(dist));
memset(visited,0,sizeof(visited));
q.push(i);
dist[i] = 0;
visited[i] = 1;
while(!q.empty()){
ll a = q.front();
q.pop();
for(auto u : v[a]){
if(visited[u] == 0 || dist[u] > dist[a] + 1){
q.push(u);
dist[u] = dist[a] + 1;
visited[u] = 1;
}
}
}
ll no = 0;
ll total = 0;
for(ll i = 0;i < N;i++){
if(visited[i] == 0){
no = 1;
break;
}
total += dist[i] + 1;
}
if(no == 0) sum = min(sum,total);
}
cout<<sum<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
312 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
4 ms |
452 KB |
Output is correct |
13 |
Correct |
4 ms |
460 KB |
Output is correct |
14 |
Correct |
135 ms |
588 KB |
Output is correct |
15 |
Correct |
9 ms |
588 KB |
Output is correct |
16 |
Correct |
520 ms |
716 KB |
Output is correct |
17 |
Correct |
733 ms |
688 KB |
Output is correct |
18 |
Correct |
683 ms |
692 KB |
Output is correct |