Submission #494342

#	Time	Username	Problem	Language	Result	Execution time	Memory
494342		ahmeteren	Bosses (BOI16_bosses)	C++17	100 / 100	1338 ms	960 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;

int cnt = 0, c[N], temp;
bool visited[N];
vector<int> adj[N], vec[N];

void bfs(int node)
{
	queue<int> q;

	q.push(node);
	visited[node] = true;
	cnt = 1;

	while(!q.empty())
	{
		int node = q.front();
		q.pop();

		for(auto to : adj[node])
		{
			if(!visited[to])
			{
				cnt++;
				visited[to] = true;
				q.push(to);
				vec[node].push_back(to);
			}
		}
	}
}

void dfs(int node, int par)
{
	for(auto to : vec[node])
	{
		if(to == par)
			continue;

		dfs(to, node);
		c[node] += c[to];
	}
	c[node]++;
	temp += c[node];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	// #ifndef ONLINE_JUDGE
	// 	freopen("in.txt", "r", stdin);
	// 	freopen("out.txt", "w", stdout);
	// #endif

	int n, cevap = 1e9;
	cin >> n;

	for(int i = 1; i <= n; i++)
	{
		int k;
		cin >> k;

		for(int j = 0; j < k; j++)
		{
			int b;
			cin >> b;

			adj[b].push_back(i);
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int i = 1; i <= n; i++)
			vec[i].clear(), visited[i] = false, c[i] = 0;

		cnt = 0;
		bfs(i);

		if(cnt == n)
		{
			temp = 0;
			dfs(i, 0);
			cevap = min(cevap, temp);
		}
	}

	cout << cevap << '\n';
	return 0;
}

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