Submission #121571

#	Time	Username	Problem	Language	Result	Execution time	Memory
121571		DodgeBallMan	Bosses (BOI16_bosses)	C++14	100 / 100	571 ms	760 KiB

bosses

#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 5e3 + 10;

int n, ans = INT_MAX;
vector<int> g[N];
int dep[N];
queue<int> q;

int bfs( int root ) {
    int ret = 0;
    for( int i = 1 ; i <= n ; i++ ) dep[i] = INT_MAX;
    dep[root] = 1;
    q.emplace( root );
    while( !q.empty() ) {
        int now = q.front(); q.pop();
        for( int i : g[now] ) if( dep[now] + 1 < dep[i] ) {
            dep[i] = dep[now] + 1;
            q.emplace( i );
        }
    }
    for( int i = 1 ; i <= n ; i++ ) {
        if( dep[i] == INT_MAX ) return INT_MAX;
        ret += dep[i];
    }
    return ret;
}

int main()
{
    scanf("%d",&n);
    for( int i = 1, k ; i <= n ; i++ ) {
        scanf("%d",&k);
        for( int j = 1, t ; j <= k ; j++ ) {
            scanf("%d",&t);
            g[t].emplace_back( i );
        }
    }
    for( int i = 1 ; i <= n ; i++ ) ans = min( ans, bfs( i ) );
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bosses.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
bosses.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&t);
             ~~~~~^~~~~~~~~

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