oj.uz

Submission #40635

# Submission time Handle Problem Language Result Execution time Memory
40635 2018-02-06T02:01:32 Z MatheusLealV Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 1340 KB 
#include <bits/stdc++.h>
#define N 5010
#define inf 2000000000
using namespace std;

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

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

inline 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;

	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);
			}
		}
	}

	dfs(root, root);

	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 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 2 ms 816 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 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 856 KB Output is correct

Subtask #3
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 816 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 6 ms 876 KB Output is correct
13 Correct 5 ms 996 KB Output is correct
14 Correct 513 ms 1260 KB Output is correct
15 Correct 95 ms 1260 KB Output is correct
16 Execution timed out 1555 ms 1340 KB Time limit exceeded
17 Halted 0 ms 0 KB -