oj.uz

답안 #371022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371022 2021-02-25T15:52:19 Z peijar Bosses (BOI16_bosses) C++17
100 / 100
 882 ms 772 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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