Submission #418159

#	Time	Username	Problem	Language	Result	Execution time	Memory
418159		T0p_	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	460 KiB

bosses

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

int salary[5005];
vector<int> children[5005], g[5005];
bool visit[5005];

void init(int n)
{
	for(int i=1 ; i<=n ; i++)
	{
		salary[i] = 0;
		g[i].clear();
		visit[i] = false;
	}
}

void dfs(int u, int &sum)
{
	int now = 1;
	for(auto x : g[u])
	{
		dfs(x, sum);
		now += salary[x];
	}
	salary[u] = now;
	sum += now;
}

int main()
{
	int n;
	scanf(" %d",&n);
	for(int i=1 ; i<=n ; i++)
	{
		int k;
		scanf(" %d",&k);
		while(k--)
		{
			int u;
			scanf(" %d",&u);
			children[u].push_back(i);
		}
	}
	int ans = 1e9;
	for(int i=1 ; i<=n ; i++)
	{
		init(n);
		queue<int> bfs;
		bfs.push(i);
		visit[i] = true;
		while(!bfs.empty())
		{
			int u = bfs.front();
			bfs.pop();
			for(auto x : children[u])
			{
				if(visit[x]) continue;
				visit[x] = true;
				g[u].push_back(x);
				bfs.push(x);
			}
		}
		int sum = 0;
		dfs(i, sum);
		ans = min(ans, sum);
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf(" %d",&n);
      |  ~~~~~^~~~~~~~~~
bosses.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf(" %d",&k);
      |   ~~~~~^~~~~~~~~~
bosses.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    scanf(" %d",&u);
      |    ~~~~~^~~~~~~~~~

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