Submission #1277233

#TimeUsernameProblemLanguageResultExecution timeMemory
1277233beheshtBosses (BOI16_bosses)C++20
100 / 100
403 ms784 KiB
#include <bits/stdc++.h>
 
#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1
 
using namespace std;
 
const int INF = 1e13 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 2e5 + 24 + (34 / 10); // 34 ---> 35
 
vector <int> adj[MAXN];
int dis[MAXN];
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
 
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
 
		for(int j = 0; j < x; j++){
			int u;
			cin >> u;
 
			u--;
 
			adj[u].pb(i);
		}
	}
 
	int ans = INF;
 
	for(int i = 0; i < n; i++){
 
		for(int j = 0; j < n; j++)
			dis[j] = INF;
 
		dis[i] = 0;
 
		queue <int> q;
		q.push(i);
 
		while(!q.empty()){
			auto u = q.front();
			q.pop();
 
			for(auto v : adj[u]){
				if(dis[v] == INF){
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
 
		int eli = n;
 
		for(int j = 0; j < n; j++)
			eli += dis[j];
 
		ans = min(ans, eli);
	}
 
	cout << ans << endl;
}
 
// Ey To Bahane! :_)))
 
// -------------<3------------- //
/*
Magasan dor shirini: 
 
1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 
 
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...