Submission #753466

#	Time	Username	Problem	Language	Result	Execution time	Memory
753466		MetalPower	Bosses (BOI16_bosses)	C++14	100 / 100	634 ms	720 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MX = 5e3 + 10;
const ll INF = 1e18;

int N, vis[MX], dep[MX];
vector<int> adj[MX];

ll bfs(int u){

	memset(vis, 0, sizeof vis);
	memset(dep, 0, sizeof dep);

	ll ans = 0, cnt = 0;
	queue<int> q; q.push(u);
	dep[u] = 1;
	vis[u] = 1;

	while(!q.empty()){

		int cr = q.front(); 
		ans += dep[cr]; cnt++;
		q.pop();

		for(int nxt : adj[cr]){
			if(vis[nxt] == 1) continue;
			vis[nxt] = 1;
			dep[nxt] = dep[cr] + 1;
			q.push(nxt);
		}
	}

	if(cnt == N) return ans;
	else return INF;
}

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

	cin >> N;
	for(int i = 1; i <= N; i++){
		int k; cin >> k;
		for(int j = 1; j <= k; j++){
			int x; cin >> x;
			adj[x].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