Submission #371022

#	Time	Username	Problem	Language	Result	Execution time	Memory
371022		peijar	Bosses (BOI16_bosses)	C++17	100 / 100	882 ms	772 KiB

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 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33