Submission #78542

#	Time	Username	Problem	Language	Result	Execution time	Memory
78542		vex	Bosses (BOI16_bosses)	C++14	100 / 100	674 ms	1020 KiB

bosses

#include <bits/stdc++.h>
#define maxn 5005
#define INF int(1e9+233)
using namespace std;

int n;
vector<int>d[maxn];
bool bio[maxn];

int dub[maxn];
queue<int>mq;
int bfs(int v)
{
    mq.push(v);
    for(int i=1;i<=n;i++)
    {
        dub[i]=-1;
        bio[i]=false;
    }
    bio[v]=true;
    dub[v]=1;
    int tre=1;
    int br=1;
    while(!mq.empty())
    {
        int u=mq.front();
        mq.pop();

        for(auto x:d[u])
        {
            if(bio[x])continue;
            mq.push(x);
            bio[x]=true;
            br++;
            dub[x]=dub[u]+1;
            tre+=dub[x];
        }
    }

    if(br<n)return INF;
    return tre;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        for(int j=0;j<x;j++)
        {
            int w;
            cin>>w;
            d[w].push_back(i);
        }
    }

    int sol=INF;
    for(int i=1;i<=n;i++)sol=min(sol,bfs(i));
    cout<<sol<<endl;
    return 0;
}

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