# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
83031 |
2018-11-04T07:56:44 Z |
FedericoS |
Bosses (BOI16_bosses) |
C++14 |
|
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;
}
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |