Submission #83031

#	Time	Username	Problem	Language	Result	Execution time	Memory
83031		FedericoS	Bosses (BOI16_bosses)	C++14	100 / 100	1000 ms	1296 KiB

bosses

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

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

bool comp(int a, int b){
	return grafo[a].size()>grafo[b].size();
}

void DFS(int k){
	for(int f:albero[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--;
			grafo[x].push_back(i);
		}
	}

	for(int i=0;i<N;i++)
		G.push_back(i);
	sort(G.begin(),G.end(),comp);

	for(int i:G){

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

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

		while(!Q.empty()){
			int nodo=Q.front();
			Q.pop();
			for(int f:grafo[nodo])
				if(!V[f]){
					Q.push(f);
					V[f]=true;
					albero[nodo].push_back(f);
					x++;
				}
		}
		
		if(x!=N)
			continue;

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

		if(clock()>CLOCKS_PER_SEC)
			break;

	}

	cout<<ans;

}

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