oj.uz

Submission #418159

# Submission time Handle Problem Language Result Execution time Memory
418159 2021-06-05T07:23:19 Z T0p_ Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 460 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 460 KB Output isn't correct
4 Halted 0 ms 0 KB -