# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
57094 |
2018-07-14T01:48:19 Z |
IvanC |
Bosses (BOI16_bosses) |
C++17 |
|
985 ms |
1708 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
const int INF = 1e9;
vector<int> grafo[MAXN];
int pai[MAXN],processado[MAXN],salario[MAXN],N;
int simula(int X){
memset(processado,0,sizeof(processado));
memset(salario,0,sizeof(salario));
//printf("Simula %d\n",X);
queue<int> bfs;
stack<int> pilha;
bfs.push(X);
pai[X] = -1;
processado[X] = 1;
while(!bfs.empty()){
int v = bfs.front();
//printf("%d ",v);
bfs.pop();
pilha.push(v);
for(int u : grafo[v]){
if(processado[u]) continue;
processado[u] = 1;
pai[u] = v;
bfs.push(u);
}
}
//printf("\n");
for(int i = 1;i<=N;i++) if(!processado[i]) return INF;
int somatorio = 0;
while(!pilha.empty()){
int v = pilha.top();
pilha.pop();
salario[v]++;
// printf("V %d S %d\n",v,salario[v]);
somatorio += salario[v];
if(pai[v] != -1) salario[pai[v]] += salario[v];
}
return somatorio;
}
int main(){
cin >> N;
for(int i = 1;i<=N;i++){
int grau;
cin >> grau;
for(int k = 1;k<=grau;k++){
int j;
cin >> j;
grafo[j].push_back(i);
}
}
int ans = simula(1);
for(int i = 2;i<=N;i++) ans = min(ans, simula(i) );
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
748 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
1084 KB |
Output is correct |
6 |
Correct |
2 ms |
1084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
748 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
1084 KB |
Output is correct |
6 |
Correct |
2 ms |
1084 KB |
Output is correct |
7 |
Correct |
3 ms |
1084 KB |
Output is correct |
8 |
Correct |
4 ms |
1084 KB |
Output is correct |
9 |
Correct |
4 ms |
1084 KB |
Output is correct |
10 |
Correct |
3 ms |
1084 KB |
Output is correct |
11 |
Correct |
5 ms |
1084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
636 KB |
Output is correct |
2 |
Correct |
2 ms |
748 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
3 ms |
972 KB |
Output is correct |
5 |
Correct |
3 ms |
1084 KB |
Output is correct |
6 |
Correct |
2 ms |
1084 KB |
Output is correct |
7 |
Correct |
3 ms |
1084 KB |
Output is correct |
8 |
Correct |
4 ms |
1084 KB |
Output is correct |
9 |
Correct |
4 ms |
1084 KB |
Output is correct |
10 |
Correct |
3 ms |
1084 KB |
Output is correct |
11 |
Correct |
5 ms |
1084 KB |
Output is correct |
12 |
Correct |
12 ms |
1084 KB |
Output is correct |
13 |
Correct |
10 ms |
1200 KB |
Output is correct |
14 |
Correct |
203 ms |
1252 KB |
Output is correct |
15 |
Correct |
19 ms |
1288 KB |
Output is correct |
16 |
Correct |
877 ms |
1564 KB |
Output is correct |
17 |
Correct |
983 ms |
1564 KB |
Output is correct |
18 |
Correct |
985 ms |
1708 KB |
Output is correct |