Submission #753465

#	Time	Username	Problem	Language	Result	Execution time	Memory
753465		MetalPower	Bosses (BOI16_bosses)	C++14	0 / 100	0 ms	468 KiB

bosses

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

#define ll long long

const int MX = 5e3 + 10;

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;
	queue<int> q; q.push(u);
	dep[u] = 1;
	vis[u] = 1;

	while(!q.empty()){

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

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

	return ans;
}

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 = 1e18;
	for(int i = 1; i <= N; i++) ans = min(ans, bfs(i));
	cout << ans << '\n';
}

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