Submission #83029

#	Time	Username	Problem	Language	Result	Execution time	Memory
83029		FedericoS	Bosses (BOI16_bosses)	C++14	67 / 100	1559 ms	19092 KiB

bosses

#include <iostream>
#include <queue>
#include <assert.h>
using namespace std;
typedef long long int ll;

ll N,K;
ll x;
bool B[5005][5005],V[5005];
int P[5005];
queue<int> L;
vector<int> grafo[5005];
ll ans=1e18,res;
ll S[5005];
int c=-1;

void DFS(int k){
	for(int f:grafo[k]){
		DFS(f);
		S[k]+=S[f];
	}
	S[k]++;
	res+=S[k];
}

int main(){

	cin>>N;
	for(int i=0;i<N;i++){
		cin>>K;
		for(int j=0;j<K;j++){
			cin>>x;
			x--;
			B[i][x]=true;
		}
	}

	for(int i=0;i<N;i++){

		fill(V,V+N,false);
		L.push(i);
		V[i]=true;

		for(int j=0;j<N;j++)
			grafo[j].clear();
		fill(S,S+N,0);
		res=0;
		x=1;

		while(!L.empty()){
			for(int j=0;j<N;j++)
				if(!V[j] and B[j][L.front()]){
					x++;
					grafo[L.front()].push_back(j);
					L.push(j);
					V[j]=true;
				}
			L.pop();
		}

		if(x!=N)
			continue;

		DFS(i);
		ans=min(ans,res);

	}

	cout<<ans;

}

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