oj.uz

Submission #24762

# Submission time Handle Problem Language Result Execution time Memory
24762 2017-06-13T08:48:31 Z nibnalin Bosses (BOI16_bosses) C++14
0 / 100
 0 ms 2316 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

const int maxn = int(5e3)+5, inf = int(1e9)+5;

int n, D[maxn], P[maxn], val[maxn];
vector<int> graph[maxn], tree[maxn];

void dfs(int node)
{
	val[node] = 1;
	for(auto it: tree[node])
	{
		dfs(it);
		val[node] += val[it];
	}
}

int solve(int node)
{
	set<pair<int, int>> Q;
	for(int i = 0;i < n;i++) D[i] = inf;
	D[node] = 0;
	Q.insert({0, node});
	P[node] = -1;
	while(!Q.empty())
	{
		pair<int, int> top = *Q.begin();
		Q.erase(Q.begin());

		for(auto it: graph[top.second])
		{
			if(D[it] > 1+D[top.second])
			{
				if(D[it] != inf) Q.erase({D[it], it});
				D[it] = 1+D[top.second];
				P[it] = top.second;
				Q.insert({D[it], it});
			}
		}
	}

	for(int i = 0;i < n;i++) tree[i].clear();

	for(int i = 0;i < n;i++)
	{
		if(P[i] != -1) tree[P[i]].push_back(i);
	}
	dfs(node);
	int ret = 0;
	for(int i = 0;i < n;i++) ret += val[i];
	//cout << "\n" << node << " " << " " << ret << "\n";
	return ret;
}

int main(void)
{
	int p, x;
	scanf("%d", &n);
	for(int i = 0;i < n;i++)
	{
		scanf("%d", &x);
		for(int j = 0;j < x;j++)
		{
			scanf("%d", &p);
			p--;
			graph[p].push_back(i);
		}
	}

	int res = inf;
	for(int i = 0;i < n;i++) res = min(res, solve(i));
	printf("%d\n", res);
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:62:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bosses.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
bosses.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &p);
                   ^

Subtask #1
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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