oj.uz

Submission #40633

# Submission time Handle Problem Language Result Execution time Memory
40633 2018-02-06T01:38:41 Z MatheusLealV Bosses (BOI16_bosses) C++14
0 / 100
 2 ms 868 KB 
#include <bits/stdc++.h>
#define N 5010
using namespace std;

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

vector<int> pai[N], 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];
}

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

	for(int i = 0; i < N; i++) grafo[i].clear(), used[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];

	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;

			pai[p].push_back(x);

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

	int ans = 2000000000;

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

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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Incorrect 2 ms 868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Incorrect 2 ms 868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Incorrect 2 ms 868 KB Output isn't correct
5 Halted 0 ms 0 KB -