Submission #626664

#	Time	Username	Problem	Language	Result	Execution time	Memory
626664		chonka	Bosses (BOI16_bosses)	C++98	100 / 100	624 ms	716 KiB

bosses

#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 ;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33