Submission #758823

#	Time	Username	Problem	Language	Result	Execution time	Memory
758823		nihon	Bosses (BOI16_bosses)	C++14	100 / 100	409 ms	696 KiB

bosses

#include <bits/stdc++.h>
#define N 5005
using namespace std;
int n,i,j,x,k,f[N],g[N],t,z,mn=2e9;
vector<int> v[N];
struct elem
{
    int x;
    int t;
}q[N];
void bfs()
{
   int st=1,dr=1,p;
   f[i]=1;
   q[st].x=i;
   q[st].t=1;
   while(st<=dr)
   {
       int y=q[st].x;
       for(j=0;j<v[y].size();++j)
       {
           if(!f[v[y][j]])
           {
               ++dr;
               ++z;
               q[dr].x=v[y][j];
               q[dr].t=q[st].t+1;
               t+=q[dr].t;
               f[v[y][j]]=1;
           }
       }
       ++st;
   }
   if(z<n) t=2e9;
}
int main()
{
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>k;
        for(j=1;j<=k;++j)
        {
            cin>>x;
            v[x].push_back(i);
        }
    }
    for(i=1;i<=n;++i)
    {
        t=1; z=1;
        for(j=1;j<=n;++j)
        {
            f[j]=0;
            g[j]=0;
        }
        bfs();
        mn=min(mn,t);
    }
    cout<<mn;
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs()':
bosses.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |        for(j=0;j<v[y].size();++j)
      |                ~^~~~~~~~~~~~
bosses.cpp:13:18: warning: unused variable 'p' [-Wunused-variable]
   13 |    int st=1,dr=1,p;
      |                  ^

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