Submission #755200

#	Time	Username	Problem	Language	Result	Execution time	Memory
755200		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	743 ms	724 KiB

bosses

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

vector <int> ke[5005];
long long oo=1000000000000000;
long long kq;
long long danhdau[5005];
queue <int> q;
long long h[5005];
int n;

void bfs(int s)
{
    long long cnt=0;
    while (q.size()) q.pop();
    q.push(s);
    long long tong=0;
    while (q.size())
    {
        int s=q.front();
        q.pop();
        for (int i=0;i<ke[s].size();i++)
        {
            int v=ke[s][i];
            if (danhdau[v]==0)
            {
                danhdau[v]=1;
                h[v]=h[s]+1;
                tong=tong+h[v];
                cnt++;
                q.push(v);
            }
        }
    }
    // cout << tong << " " << s << '\n';
    if (cnt==n-1) kq=min(kq,tong+1);
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        int kk;
        cin >> kk;
        for (int i2=1;i2<=kk;i2++)
        {
            int kkk;
            cin >> kkk;
            ke[kkk].push_back(i);
        }
    }
    kq=oo;
    for (int dinh=1;dinh<=n;dinh++)
    {
        for (int i=1;i<=n;i++)
        {
            danhdau[i]=0;
            h[i]=0;
        }
        h[dinh]=1;
        danhdau[dinh]=1;
        if (!ke[dinh].size()) continue;
        bfs(dinh);
    }
    cout << kq;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:22:23: 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<ke[s].size();i++)
      |                      ~^~~~~~~~~~~~~

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