# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
626664 |
2022-08-11T15:36:26 Z |
chonka |
Bosses (BOI16_bosses) |
C++ |
|
624 ms |
716 KB |
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 5007 ;
int n ;
vector < int > v[ MAXN ] ;
int dist[ MAXN ] ;
queue < int > q ;
int bfs ( int ori ) {
for ( int i = 1 ; i <= n ; ++ i ) {
dist[ i ] = MAXN ;
}
int ret = 0 ;
dist[ ori ] = 1 ;
q.push ( ori ) ;
while ( q.empty ( ) == false ) {
int x = q.front ( ) ; q.pop ( ) ;
ret += dist[ x ] ;
for ( auto y : v[ x ] ) {
if ( dist[ y ] == MAXN ) {
dist[ y ] = dist[ x ] + 1 ;
q.push ( y ) ;
}
}
}
for ( int i = 1 ; i <= n ; ++ i ) {
if ( dist[ i ] == MAXN ) { return MAXN * MAXN ; }
}
return ret ;
}
void solve ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
int sz ; cin >> sz ;
for ( int j = 0 , x ; j < sz ; ++ j ) {
cin >> x ;
v[ x ].push_back ( i ) ;
}
}
int ans = MAXN * MAXN ;
for ( int i = 1 ; i <= n ; ++ i ) {
ans = min ( ans , bfs ( i ) ) ;
}
cout << ans << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
444 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
444 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
468 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
117 ms |
552 KB |
Output is correct |
15 |
Correct |
10 ms |
452 KB |
Output is correct |
16 |
Correct |
484 ms |
716 KB |
Output is correct |
17 |
Correct |
624 ms |
660 KB |
Output is correct |
18 |
Correct |
611 ms |
656 KB |
Output is correct |