Submission #1270417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270417		k12_khoi	Bosses (BOI16_bosses)	C++17	100 / 100	367 ms	744 KiB

bosses

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

const int N=5005;
const int oo=1e9+1;

int n,k,x,y,sum,res;
int a[N],salary[N],step_father[N];
bool used[N];
vector <int> g[N];

namespace sub1
{
    void ql(int i)
    {
        if (i>n)
        {
            for (int i=1;i<=n;i++)
            salary[i]=1;

            for (int i=n;i>1;i--)
            salary[step_father[a[i]]]+=salary[a[i]];

            sum=0;
            for (int i=1;i<=n;i++)
            sum+=salary[i];

            res=min(res,sum);

            return;
        }

        for (int j=1;j<i;j++)
        {
            int u=a[j];

            for (int v:g[u])
            if (!used[v])
            {
                used[v]=true;
                a[i]=v;
                step_father[v]=u;

                ql(i+1);

                step_father[v]=0;
                a[i]=0;
                used[v]=false;
            }
        }
    }

    void solve()
    {
        res=oo;
        for (int i=1;i<=n;i++)
        {
            used[i]=true;
            a[1]=i;
            step_father[i]=0;

            ql(2);

            a[1]=0;
            used[i]=false;
        }

        cout << res;
    }
}

namespace sub3
{
    queue <int> q;

    int bfs(int u)
    {
        for (int i=1;i<=n;i++)
        salary[i]=oo;

        salary[u]=1;
        q.push(u);

        while (!q.empty())
        {
            u=q.front();
            q.pop();

            for (int v:g[u])
            if (salary[v]>salary[u]+1)
            {
                salary[v]=salary[u]+1;
                q.push(v);
            }
        }

        int sum=0;
        for (int i=1;i<=n;i++)
        {
            if (salary[i]==oo) return oo;
            sum+=salary[i];
        }

        return sum;
    }

    void solve()
    {
        res=oo;
        for (int i=1;i<=n;i++)
        res=min(res,bfs(i));

        cout << res;
    }
}

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

    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> k;

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

    sub3::solve();
}

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