제출 #350578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
350578		saniyar_krmi	Bosses (BOI16_bosses)	C++14	100 / 100	778 ms	896 KiB

bosses

// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#define int long long 
#pragma GCC optimize ("Ofast")

//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int maxn = 5000 + 10;
const ll inf = 1e18 + 10;
int n;
vector <int> G[maxn];
bool mark[maxn];
int d[maxn];

ll bfs(int src){
	fill(mark, mark+maxn, 0);
	fill(d, d+maxn, 0);

	queue <int> q;
	q.push(src);
	mark[src] = 1;
	d[src] = 1;

	ll res = 0;
	while(!q.empty()){
		int v = q.front();
		q.pop();

		for(int u: G[v]){
			if(mark[u])
				continue;
			mark[u] = 1;
			d[u] = d[v] + 1;
			q.push(u);
		}
	}

	for(int i=1; i<=n; i++){
		if(d[i] == 0)
			return inf;
		res += d[i];
	}

	return res;
}

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

	cin >> n;
	int k;
	for(int i=1; i<=n; i++){
		cin >> k;
		int p;
		for(int j=0; j<k; j++){
			cin >> p;
			G[p].push_back(i);
		}
	}

	ll ans = inf;
	for(int i=1; i<=n; i++)
		ans = min(ans, bfs(i));

	cout << ans << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33