Submission #220153

#	Time	Username	Problem	Language	Result	Execution time	Memory
220153		MKopchev	Bosses (BOI16_bosses)	C++14	100 / 100	803 ms	760 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
const int nmax=5e3+42,inf=1e4+42;
int n;
vector<int> adj[nmax];

int dist[nmax];

queue< pair<int/*node*/,int/*dist*/> > q;

int bfs(int start)
{
    for(int i=1;i<=n;i++)dist[i]=inf;

    q.push({start,1});

    while(q.size())
    {
        pair<int/*node*/,int/*dist*/> cur=q.front();
        q.pop();

        if(dist[cur.first]!=inf)continue;

        dist[cur.first]=cur.second;
        for(auto k:adj[cur.first])
            q.push({k,cur.second+1});
    }

    int ret=0;
    for(int i=1;i<=n;i++)ret=ret+dist[i];

    //cout<<start<<" -> ";for(int i=1;i<=n;i++)cout<<dist[i]<<" ";cout<<endl;

    return ret;
}
int main()
{
    scanf("%i",&n);

    for(int i=1;i<=n;i++)
    {
        int sz,u;
        scanf("%i",&sz);
        for(int j=1;j<=sz;j++)
        {
            scanf("%i",&u);
            adj[u].push_back(i);
        }
    }

    int output=n*n;
    for(int i=1;i<=n;i++)
        output=min(output,bfs(i));

    printf("%i\n",output);
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
bosses.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&sz);
         ~~~~~^~~~~~~~~~
bosses.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&u);
             ~~~~~^~~~~~~~~

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