Submission #1086426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086426		hahahaha	Bosses (BOI16_bosses)	C++17	100 / 100	408 ms	680 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
bool ok = 0;
 
 
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:11:25: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | int n , h[maxn] , ans = 1e18;
      |                         ^~~~

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