Submission #1044273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044273		vjudge1	Bosses (BOI16_bosses)	C++14	100 / 100	353 ms	724 KiB

bosses

#include <bits/stdc++.h>
#define ll long long

using namespace std;


const int maxn = 5000 + 7;

int n , h[maxn] , ans = 1e18;
vector <int> g[maxn];

void bfs(int s)
{
    for(int i = 1; i <= n; i++) h[i] = -1;
    queue <int> node;
    node.push(s);

    h[s] = 1;

    while(!node.empty())
    {
        int u = node.front();
        for(int v: g[u])
        {
            if(h[v] == -1)
            {
                h[v] = h[u] + 1;
                node.push(v);
            }
        }
        node.pop();
    }

    int cnt = 0;
    bool check = 1;

    for(int i = 1; i <= n; i++)
    {
        if(h[i] == -1) check = 0;
        cnt += h[i];
    }

    if(check) ans = min(ans , cnt);
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int s , k; cin >> s;
        while(s--)
        {
            cin >> k;
            g[k].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        bfs(i);
    }

    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

bosses.cpp:9:25: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | int n , h[maxn] , ans = 1e18;
      |                         ^~~~

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