Submission #218098

#	Time	Username	Problem	Language	Result	Execution time	Memory
218098		Alexa2001	Bosses (BOI16_bosses)	C++17	100 / 100	743 ms	760 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

///10:45

typedef long long ll;
const int Nmax = 5005;

vector<int> v[Nmax];
int n, d[Nmax];


ll solve(int start)
{
    queue<int> q;
    memset(d, 0, sizeof(d));

    q.push(start);
    d[start] = 1;

    ll ans = 1;
    int nr = 1;

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : v[node])
            if(!d[it])
            {
                ++nr;
                d[it] = d[node] + 1;
                ans += d[it];
                q.push(it);
            }
    }
    if(nr != n) return LLONG_MAX;
    return ans;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n;

    int i;
    for(i=1; i<=n; ++i)
    {
        int nr;
        cin >> nr;
        while(nr--)
        {
            int x;
            cin >> x;
            v[x].push_back(i);
        }
    }

    ll ans = LLONG_MAX;
    for(i=1; i<=n; ++i)
        ans = min(ans, solve(i));

    cout << ans << '\n';

    return 0;
}

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