Submission #77148

#	Time	Username	Problem	Language	Result	Execution time	Memory
77148		Mercenary	Bosses (BOI16_bosses)	C++11	100 / 100	542 ms	1432 KiB

bosses

#include<bits/stdc++.h>

using namespace std;
#define taskname ""
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 5e3 + 5;
int n , deq[maxn] , sz , chk[maxn];
int res = (ll)1e9;
vector<int> v[maxn];
int sum = 0;
void BFS(int u)
{
    fill_n(chk , maxn , 0);
    deq[0] = u;
    sz = 1;
    chk[u] = 1;
    int edgecount = 0;
    sum = 1;
    int it = 0;
    while(sz > it)
    {
        int from = deq[it];
        ++it;
        for(int c : v[from])
            if(chk[c] == 0)
            {
                chk[c] = chk[from] + 1;
                sum += chk[c];
                deq[sz++] = c;
                edgecount++;
            }
    }
    if(edgecount == n - 1){
        res = min(res , sum);
    }
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen(taskname".INP", "r",stdin);
	//freopen(taskname".OUT", "w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        int k;cin >> k;
        while(k--)
        {
            int x;cin >> x;
            v[x].pb(i);
        }
    }
    for(int i = 1 ; i <= n ; ++i)BFS(i);
    cout << res;
}
/*
    4
    1 4
    3 1 3 4
    2 1 2
    1 3
*/

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