Submission #290276

#	Time	Username	Problem	Language	Result	Execution time	Memory
290276		MasterTaster	Bosses (BOI16_bosses)	C++14	100 / 100	755 ms	896 KiB

bosses

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"

vector<int> g[5010], p[15];
ll n, k[5010], koga[15], trRess;
//bool bio[15];
ll ress;

ll d[5010];
bool bio[5010];

int dfs(int u)
{
    bio[u]=true;
    //cout<<u<<endl;
    int suma=0;
    for (auto v:g[u])
    {
        if (!bio[v])
        {
            suma+=dfs(v);
        }
    }
    trRess+=suma+1;
    return (suma)+1;
}

void popravi()
{
    int koliko=0, root=-1;
    for (int i=1; i<=n; i++)
    {
        if (koga[i]==-1) { koliko++; root=i; }
    }

    if (koliko!=1) return;

    for (int i=1; i<=n; i++) { g[i].clear(); bio[i]=false; }
    for (int i=1; i<=n; i++) { if (i!=root) g[koga[i]].pb(i); }

    trRess=0;
    dfs(root);

    for (int i=1; i<=n; i++) if (!bio[i]) return;

    //for (int i=1; i<=n; i++) cout<<koga[i]<<" ";
    //cout<<endl<<trRess<<endl;
    ress=min(ress, trRess);
}

void uradi(int x, bool bio)
{
    if (x==n+1)
    {
        popravi();
        return;
    }

    if (!bio) { koga[x]=-1; uradi(x+1, true); }
    for (int i=0; i<k[x]; i++)
    {
        koga[x]=p[x][i];
        uradi(x+1, bio);
    }
}

ll bfs(int s)
{
    queue<int> q;
    q.push(s);
    d[s]=1;
    bio[s]=true;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (auto v:g[u])
        {
            if (!bio[v])
            {
                d[v]=d[u]+1;
                bio[v]=true;
                q.push(v);
            }
        }
    }

    for (int i=1; i<=n; i++) if (!bio[i]) return 1000000010;

    ll ret=0;
    for (int i=1; i<=n; i++) ret+=d[i];
    return ret;
}

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

    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>k[i];
        for (int j=0; j<k[i]; j++)
        {
            int x; cin>>x;
            g[x].pb(i);
        }
    }

    //ress=1010;
    //uradi(1, 0);

    ress=10000010;
    for (int i=1; i<=n; i++)
    {
        for (int i=1; i<=n; i++) bio[i]=false;
        trRess=bfs(i);
        //cout<<trRess<<endl;
        ress=min(ress, trRess);
    }

    cout<<ress;
}

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