oj.uz

Submission #676204

# Submission time Handle Problem Language Result Execution time Memory
676204 2022-12-29T20:15:41 Z mseebacher Bosses (BOI16_bosses) C++17
0 / 100
 4 ms 7368 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7368 KB Output isn't correct
3 Halted 0 ms 0 KB -