Submission #884298

#	Time	Username	Problem	Language	Result	Execution time	Memory
884298		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	2652 KiB

bosses

// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mk make_pair
#define ppb pop_back
#define endl '\n'
#define pii pair<int, int>
#define sz(x) (int)x.size()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O4")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, maxn = 1e5 + 10, inf = 1e9 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;

vector<vector<int>> g(maxn);
int n, ans = inf;

void bfs(int v){
	vector<int> dist(n, inf);
	map<int, int> t;
	dist[v] = 0;
	queue<int> q;
	q.push(v);
	while(q.size()){
		int u = q.front();
		q.pop();
		for(int v : g[u]){
			if(dist[v] > dist[u] + 1){
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	if(*max_element(all(dist)) == inf) return;
	for(int i = 0; i < n; ++i) t[dist[i]]++;
	int x = 1, anss = 1;
	for(int i = n - 1; i >= 0; --i){
		anss += x;
		x += t[i];
	}
	ans = min(ans, anss);
}
signed main(){
	fast();
	cin >> n;
	for(int i = 0; i < n; ++i){
		int t; cin >> t;
		for(int j = 0; j < t; ++j){
			int u; cin >> u;
			u--;
			g[i].pb(u);
		}
	}
	for(int i = 0; i < n; ++i){
		bfs(i);
	}
	cout << ans;
}
// Running from the daylight...

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