Submission #77146

#	Time	Username	Problem	Language	Result	Execution time	Memory
77146		Mercenary	Bosses (BOI16_bosses)	C++14	0 / 100	2 ms	744 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] , res = (int)1e9;
vector<int> v[maxn] , v1[maxn];
int sum = 0;
int DFS(int u)
{
    int must = 1;
    for(int c : v1[u])
        must += DFS(c);
    sum += must;
    return must;
}
void BFS(int u)
{
    fill_n(chk , n + 1 , 0);
    for(int i = 1 ; i <= n ; ++i)v1[i].clear();
    deq[0] = u;
    sz = 1;
    chk[u] = 1;
    int edgecount = 0;
    while(sz > 0)
    {
        int from = deq[--sz];
        for(int c : v[from])
            if(chk[c] == 0)
            {
                v1[from].pb(c);
                chk[c] = 1;
                deq[sz++] = c;
                edgecount++;
            }
    }
    if(edgecount == n - 1){
        sum = 0;
        DFS(u);
        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: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33