Submission #57094

#	Time	Username	Problem	Language	Result	Execution time	Memory
57094		IvanC	Bosses (BOI16_bosses)	C++17	100 / 100	985 ms	1708 KiB

bosses

#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;
}

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