제출 #40636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40636		MatheusLealV	Bosses (BOI16_bosses)	C++14	100 / 100	1186 ms	1388 KiB

bosses

#include <bits/stdc++.h>
#define N 5001
#define inf 2000000000
using namespace std;

int n, used[N], dp[N];

vector<int> filho[N], grafo[N];

int dfs(int x, int p)
{
	dp[x] = 1;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		dp[x] += dfs(v, x);
	}

	return dp[x];
}

inline int add(int root)
{
	queue<int> bfs;

	for(int i = 1; i <= n; i++) grafo[i].clear(), used[i] = 0, dp[i] = 0;

	bfs.push(root), used[root] = 1, dp[root] = 1;

	while(!bfs.empty())
	{
		int x = bfs.front();

		bfs.pop();

		for(auto v: filho[x])
		{
			if(!used[v])
			{
				used[v] = 1;

				grafo[x].push_back(v);

				grafo[v].push_back(x);

				bfs.push(v);

				dp[v] = dp[x] + 1;
			}
		}
	}

	int cnt = 0;

	for(int i = 1; i <= n; i++)
	{
		cnt += dp[i];

		if(!dp[i]) cnt = inf;
	}

	return cnt;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int p = 1, k, x; p <= n; p++)
	{
		cin>>k;

		for(int it = 1; it <= k; it ++)
		{
			cin>>x;

			filho[x].push_back(p);
		}
	}

	int ans = 2000000000;

	for(int root = 1; root <= n; root ++) ans = min(ans, add(root));

	cout<<ans<<"\n";
}

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