Submission #1281066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281066		david_g611	Bosses (BOI16_bosses)	C++20	100 / 100	451 ms	728 KiB

bosses

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NMAX=5000;
int n, ans=1e9;
bool viz[NMAX+1];

vector<int> g[NMAX+1];
void bfs(int nod)
{
    int now_ans=0;
    queue<pair<int, int>> q;
    q.push({nod, 1});
    viz[nod]=1;
    while(q.size())
    {
        auto &[p, d]=q.front();
        q.pop();
        now_ans+=d;
        for(auto &vecin:g[p])
            if(!viz[vecin])
            {
                viz[vecin]=1;
                q.push({vecin, d+1});
            }
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            return;
    ans=min(ans, now_ans);
}
signed main()
{
    cin>>n;
    for(int i=1, cati, x; i<=n; i++)
    {
        cin>>cati;
        while(cati--)
        {
            cin>>x;
            g[x].push_back(i);
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(auto &x:viz)x=0;
        bfs(i);
    }
    cout<<ans;
    return 0;
}

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