Submission #371022

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
371022	2021-02-25T15:52:19 Z	peijar	Bosses (BOI16_bosses)	C++17	100 / 100	882 ms	772 KB

bosses

#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

template<typename... Args>
void read(Args&... args)
{
	((cin >> args), ...);
}
template<typename T>
void read(vector<T> &vec)
{
	for (auto &v : vec) read(v);
}

void write() {}
template<typename H, typename... T>
void write(const H &h, const T&... t)
{
	cout << h;
	if (sizeof...(t)) {cout << ' '; write(t...);}
}

template<typename T>
void write(const vector<T> &vec)
{
	if (SZ(vec) == 0) return;
	write(vec[0]);
	for (int i(1); i < SZ(vec); ++i)
	{cout << ' '; write(vec[i]);}
}

template<typename... Args>
void writeln(Args... args)
{
	write(args...); cout << '\n';
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbEmployes;
	read(nbEmployes);
	vector<vector<int>> filsPossibles(nbEmployes);
	
	for (int i(0); i < nbEmployes; ++i)
	{
		int nbParents;
		read(nbParents);
		for (int j(0); j < nbParents; ++j)
		{
			int p;
			read(p);
			p--;
			filsPossibles[p].push_back(i);
		}
	}
	ll sol(1e18);
	for (int racine(0); racine < nbEmployes; ++racine)
	{
		queue<int> q;
		vector<ll> dis(nbEmployes, 1e9);
		dis[racine] = 1;
		q.push(racine);
		while (!q.empty())
		{
			int u = q.front(); q.pop();
			for (auto v : filsPossibles[u])
				if (dis[v] == 1e9)
				{
					q.push(v);
					dis[v] = dis[u] + 1;
				}
		}
		ll cost(0);
		for (auto d :  dis)
			cost += d;
		sol = min(sol, cost);
	}
	writeln(sol);
}

Subtask #1

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct

Subtask #2

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #3

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	6 ms	492 KB	Output is correct
13	Correct	5 ms	492 KB	Output is correct
14	Correct	169 ms	748 KB	Output is correct
15	Correct	28 ms	620 KB	Output is correct
16	Correct	659 ms	752 KB	Output is correct
17	Correct	857 ms	772 KB	Output is correct
18	Correct	882 ms	772 KB	Output is correct