Submission #569143

#	Time	Username	Problem	Language	Result	Execution time	Memory
569143		beaconmc	Bosses (BOI16_bosses)	C++14	67 / 100	1566 ms	1212 KiB

bosses

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;
ll n;
vector<vector<ll>> bosses;
vector<ll> edges[5001];
vector<ll> newedges[5001];


ll sum = 0;


int dfs(ll a){

	ll sus = 1;
	for (auto&i : newedges[a]){
		sus += dfs(i);
	}
	sum += sus;
	return sus;
}

ll solve(ll a){
	FOR(i,0,5001){
		edges[i] = {};
		newedges[i] = {};
	}
	FOR(i,0,n){
		for (auto&j : bosses[i]){
			edges[j].push_back(i+1);
		}
	}
	vector<bool> visited(n+1);

	queue<ll> q;
	q.push(a);
	visited[a] = 1;

	while (q.size()){
		ll node = q.front();
		q.pop();
		for (auto&i : edges[node]){
			if (!visited[i]){
				q.push(i);
				visited[i] = 1;
				newedges[node].push_back(i);
			}
		}
	}
	sum = 0;
	dfs(a);
	FOR(i,1,n+1){
		if (!visited[i]) return 1000000000;
	}
	return sum;
}




int main(){
	cin >> n;

	FOR(i,0,n){
		ll temp; cin >> temp;
		vector<ll> templis(temp);
		FOR(i,0,temp) cin >> templis[i];
		bosses.push_back(templis);
	}
	ll mini = 1000000000;
	FOR(i,1,n+1){
		mini = min(mini, solve(i));

	}
	cout << mini;
}

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