Submission #304630

#	Time	Username	Problem	Language	Result	Execution time	Memory
304630		dolijan	Bosses (BOI16_bosses)	C++14	100 / 100	798 ms	760 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
const int mn=5069;
vector<vector<int> > graf(mn);
int kolko=0;
int bfs(int node,int n)
{
    bool visited[n+1];
    int level[n+1];
    for(int i=1;i<=n;i++) visited[i]=false;
    queue<int> q;
    q.push(node);
    visited[node]=true;
    int rez=0;
    level[node]=1;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        rez+=level[t];
        kolko++;
        for(int i=0;i<graf[t].size();i++)
        {
            if(!visited[graf[t][i]])
            {
                q.push(graf[t][i]);
                level[graf[t][i]]=level[t]+1;
                visited[graf[t][i]]=true;
            }
        }
    }
    return rez;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        int inp;
        for(int j=0;j<k;j++)
        {
            cin>>inp;
            graf[inp].push_back(i);
        }
    }
    int mn=n*n;
    for(int i=1;i<=n;i++)
    {
        kolko=0;
        int sta=bfs(i,n);
        //cout<<i<<" "<<kolko<<endl;
        if(kolko==n)
        {
            //cout<<i<<sta<<endl;
            mn=min(mn,sta);
        }
    }
    cout<<mn<<endl;
}

Compilation message (stderr)

bosses.cpp: In function 'int bfs(int, int)':
bosses.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=0;i<graf[t].size();i++)
      |                     ~^~~~~~~~~~~~~~~

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