Submission #253180

#	Time	Username	Problem	Language	Result	Execution time	Memory
253180		Blagojce	Bosses (BOI16_bosses)	C++11	100 / 100	801 ms	704 KiB

bosses

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5000;

vector<int> g[mxn]; 
int n;
 
int root(int u){
	queue<int> Q;
	Q.push(u);
	int dep[n];
	memset(dep, -1, sizeof(dep));
	dep[u] = 0;
	
	bool vis[n];
	memset(vis, false, sizeof(vis));
	vis[u] = true;
	
	while(!Q.empty()){
		int c = Q.front();
		Q.pop();
		for(auto e : g[c]){
			if(!vis[e]){
				vis[e] = true;
				dep[e] = dep[c]+1;
				Q.push(e);
			}
		}
	}
	fr(i, 0, n){
		if(!vis[i]) return i_inf;
	}
	
	int cnt[n];
	memset(cnt, 0, sizeof(cnt));
	fr(i, 0, n) cnt[dep[i]] ++;
	
	int ans = 0;
	int carry = 0;
	for(int i = n-1; i >= 0; i --){
		ans += carry + cnt[i];
		carry += cnt[i];
		
	}
	return ans;

}


void solve(){
	cin >> n;
	fr(i, 0, n){
		int k;
		cin >> k;
		fr(j, 0, k){
			int x;
			cin >> x;
			g[x-1].pb(i);
		}
	}
	int ans = i_inf;
	fr(i,0,n){
		ans = min(ans, root(i));
	}
	cout<<ans<<endl;
}

 
int main(){
	solve();
}

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