Submission #1293747

#TimeUsernameProblemLanguageResultExecution timeMemory
1293747muhammad-ahmadBosses (BOI16_bosses)C++20
0 / 100
1 ms572 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

const int N = 5e3 + 5;
int n, dist[N], vis[N], val[N];
vector<int> adj[N];

int bfs(int s){
	queue<int> q;
	q.push(s);
	
	for (int i = 0; i < N; i++) {dist[i] = 1e18; vis[i] = 0, val[i] = 0;}
	dist[s] = 0;
	
	while (q.size()){
		int u = q.front(); q.pop();
		for (auto v : adj[u]){
			if (dist[v] > dist[u] + 1){
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	
	int ans = 0;
	
	vector<pair<int, int>> v;
	
	for (int i = 1; i <= n; i++) v.push_back({dist[i], i});
	sort(rall(v));
	
	for (auto [D, i] : v){
		int s = 0;
		for (auto j : adj[i]){
			if (dist[j] == dist[i] + 1 && vis[j] == 0){
				vis[j] = 1;
				s += val[j];
			} 
		}
		val[i] = s + 1;
		ans += val[i];
	}
	
	return ans;
	
}
	
void solve() {
	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);
		}
	}	
	
	int ma = 1e18;
	for (int i = 1; i <= n; i++){
		ma = min(ma, bfs(i));
	}
	
	cout << ma << endl;
	
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...