Submission #676204

#	Time	Username	Problem	Language	Result	Execution time	Memory
676204		mseebacher	Bosses (BOI16_bosses)	C++17	0 / 100	4 ms	7368 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
vector<int> ad[3*MAXI+1];
 queue<int> q;
int dist[200001];
int bfs(int x,int n){
	vector<bool> visi(n+1,0);
	q.push(x);
	ll cost = 1;
	dist[x] = 1;
	int cntr = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		if(visi[u]) continue;
		visi[u] = true;
		for(auto s: ad[u]){
			if(!visi[s]){
				dist[s] = dist[u]+1;
				cost+=dist[s];
				q.push(s);
				cntr++;
			}
		}
	}
	return cntr == n ? cost: 1e9;
}
 
void solve(){
	
	int n; cin >> n;
	
	for(int i = 1;i<=n;i++){
		int x; cin >> x;
		for(int j = 0;j<x;j++){
			int g; cin >> g;
			ad[g].push_back(i);
		}
	}
	int mini = 1e9;
	for(int i = 1;i<=n;i++) {
		mini = min(mini,bfs(i,n));
	}
	cout << mini;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout << fixed << setprecision(8);
 
   int t = 1;
  // cin >> t;
   while(t){
	solve();
	t--;  
	cout << "\n";
   }
   return 0;
}

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