oj.uz

Submission #405174

# Submission time Handle Problem Language Result Execution time Memory
405174 2021-05-15T20:20:25 Z T0p_ Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 588 KB 
#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

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.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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