Submission #753463

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

bosses

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

#define ll long long

const int MX = 2e5 + 10;

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

ll bfs(int u){

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

	while(!q.empty()){

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

		for(int nxt : adj[cr]){
			if(vis[nxt] == off) continue;
			vis[nxt] = off;
			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++){
		off++;
		ans = min(ans, bfs(i));
	}
	cout << ans << '\n';
}

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