Submission #815410

#	Time	Username	Problem	Language	Result	Execution time	Memory
815410		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	441 ms	632 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 5000 + 5;
vector<ll> edges[maxn];
bool visited[maxn];
ll depth[maxn];
ll n, k, tmp;
ll nigga(ll u)
{
    memset(visited, false, sizeof(visited));
    memset(depth, 0, sizeof(depth));
    queue<ll> bfs;
    bfs.push(u);
    visited[u] = true;
    depth[u] = 1;
    ll total = 0;

    while (!bfs.empty())
    {
        ll sex = bfs.front();
        bfs.pop();
        total += depth[sex];
        for (auto v:edges[sex])
        {
            if (visited[v]) continue;
            visited[v] = true;
            depth[v] = depth[sex] + 1;
            bfs.push(v);

        }
    }
    bool valid = true;
    for (ll i = 1; i <= n; ++i) if (!visited[i]) valid = false;

    if (valid) return total;
    else return 1e18;
}
int main()
{

    cin >> n;

    for (ll i = 1; i <= n; ++i)
    {
        cin >> k;
        for (ll j = 1; j <= k; ++j) 
        {
            cin >> tmp;
            edges[tmp].push_back(i);
        }
    }
    ll ans = 1e18;
    for (ll i = 1; i <= n; ++i) ans = min(ans, nigga(i));
    cout << ans;

}

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