oj.uz

Submission #83027

# Submission time Handle Problem Language Result Execution time Memory
83027 2018-11-04T07:41:59 Z FedericoS Park (BOI16_park) C++14
0 / 100
 3 ms 900 KB 
#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;
		if(!K)
			c=i;
		for(int j=0;j<K;j++){
			cin>>x;
			x--;
			B[i][x]=true;
		}
	}

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

		if(c!=-1 and c!=i)
			continue;
		
		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;

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

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

	}

	cout<<ans;

}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -