oj.uz

Submission #40636

# Submission time Handle Problem Language Result Execution time Memory
40636 2018-02-06T02:12:37 Z MatheusLealV Bosses (BOI16_bosses) C++14
100 / 100
 1186 ms 1388 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 824 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 2 ms 824 KB Output is correct
8 Correct 2 ms 824 KB Output is correct
9 Correct 2 ms 824 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 2 ms 824 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 2 ms 824 KB Output is correct
8 Correct 2 ms 824 KB Output is correct
9 Correct 2 ms 824 KB Output is correct
10 Correct 2 ms 824 KB Output is correct
11 Correct 2 ms 824 KB Output is correct
12 Correct 6 ms 860 KB Output is correct
13 Correct 5 ms 1108 KB Output is correct
14 Correct 308 ms 1144 KB Output is correct
15 Correct 87 ms 1144 KB Output is correct
16 Correct 999 ms 1228 KB Output is correct
17 Correct 1186 ms 1260 KB Output is correct
18 Correct 1182 ms 1388 KB Output is correct