oj.uz

답안 #83031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83031 2018-11-04T07:56:44 Z FedericoS Bosses (BOI16_bosses) C++14
100 / 100
 1000 ms 1296 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 836 KB Output is correct
10 Correct 3 ms 836 KB Output is correct
11 Correct 3 ms 836 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 836 KB Output is correct
10 Correct 3 ms 836 KB Output is correct
11 Correct 3 ms 836 KB Output is correct
12 Correct 13 ms 864 KB Output is correct
13 Correct 12 ms 864 KB Output is correct
14 Correct 234 ms 1064 KB Output is correct
15 Correct 59 ms 1064 KB Output is correct
16 Correct 796 ms 1296 KB Output is correct
17 Correct 1000 ms 1296 KB Output is correct
18 Correct 1000 ms 1296 KB Output is correct