Submission #546121

#	Time	Username	Problem	Language	Result	Execution time	Memory
546121		Hanksburger	Bosses (BOI16_bosses)	C++17	100 / 100	1392 ms	984 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
vector<long long> adj[5005], child[5005];
bool visited[5005];
queue<long long> q;
long long a[5005];
void dfs(long long u)
{
	long long sum=0;
	for (long long i=0; i<child[u].size(); i++)
	{
		long long v=child[u][i];
		dfs(v);
		sum+=a[v];
	}
	a[u]=sum+1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n, ans=1e18;
	cin >> n;
	for (long long i=1; i<=n; i++)
	{
		long long x;
		cin >> x;
		for (long long j=1; j<=x; j++)
		{
			long long u;
			cin >> u;
			adj[u].push_back(i);
		}
	}
	for (long long i=1; i<=n; i++)
	{
		for (long long j=1; j<=n; j++)
		{
			child[j].clear();
			visited[j]=0;
		}
		visited[i]=1;
		q.push(i);
		while (!q.empty())
		{
			long long u=q.front();
			q.pop();
			for (long long j=0; j<adj[u].size(); j++)
			{
				long long v=adj[u][j];
				if (!visited[v])
				{
					child[u].push_back(v);
					visited[v]=1;
					q.push(v);
				}
			}
		}
		bool ok=1;
		for (long long j=1; j<=n; j++)
		{
			if (!visited[j])
			{
				ok=0;
				break;
			}
		}
		if (ok)
		{
			dfs(i);
			long long sum=0;
			for (long long j=1; j<=n; j++)
				sum+=a[j];
			ans=min(ans, sum);
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void dfs(long long int)':
bosses.cpp:10:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for (long long i=0; i<child[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:49:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for (long long j=0; j<adj[u].size(); j++)
      |                        ~^~~~~~~~~~~~~~

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