Submission #405174

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

bosses

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

int ans;
int deg_in[5050], deg_out[5050], sub[5050];
bool mark[5050], pushed[5050];
vector<int> g[5050], gt[5050], edge[5050];

void dfs(int u)
{
	sub[u] = 1;
	for(auto x : edge[u])
	{
		dfs(x);
		sub[u] += sub[x];
	}
	ans += sub[u];
}

int main()
{
	int n;
	scanf(" %d",&n);
	for(int i=1 ; i<=n ; i++)
	{
		scanf(" %d",&deg_in[i]);
		for(int j=1 ; j<=deg_in[i] ; j++)
		{
			int d;
			scanf(" %d",&d);
			g[d].push_back(i);
			gt[i].push_back(d);
			deg_out[d]++;
		}
	}
	int root;
	for(int i=1 ; i<=n ; i++)
	{
		int u = 0;
		for(int j=1 ; j<=n ; j++)
		{
			if(mark[j]) continue;
			if(deg_out[j] > deg_out[u]) u = j;
		}
		mark[u] = true;
		if(i == 1) root = u;
		for(auto x : g[u])
		{
			if(mark[x] || pushed[x]) continue;
			pushed[x] = true;
			edge[u].push_back(x);
		}
		for(auto x : gt[u])
		{
			deg_out[x]--;
		}
	}
	dfs(root);
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf(" %d",&n);
      |  ~~~~~^~~~~~~~~~
bosses.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf(" %d",&deg_in[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
bosses.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |    scanf(" %d",&d);
      |    ~~~~~^~~~~~~~~~
bosses.cpp:58:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  dfs(root);
      |  ~~~^~~~~~

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