Trafico IOI

Trafic.cpp

#include<iostream>
#include<cstdlib>
using namespace std;
#define MAX 1000000
#define max(a,b) (a>b)? a:b
#define min(a,b) (a<b)? a:b

typedef struct list_node {
    int node;
    int ari;
    struct list_node *next;
} llnode;

int P[MAX],S[MAX-1],D[MAX-1],sum[MAX],Sa[MAX],Da[MAX],maximo[MAX];
llnode * cam[MAX];

void add(int ndeh, int arih, int node_in, int ){
    llnode *tmp;
    tmp=(llnode*)malloc(sizeof(llnode));
    tmp->node = node_in;
    tmp->ari = arih;
    tmp->next = cam[ndeh]->next;
    cam[ndeh]->next = tmp;
}
void calcular(int nod,llnode *act){
    if(sum[nod]==-1){
        sum[nod]=P[nod];
        calcular(nod,act->next);
    }
    else if(act!=NULL){
        if(sum[act->node]==-1){
            calcular(act->node,cam[act->node]);
            sum[nod]+=sum[act->node];
        }
        calcular(nod,act->next);
    }
}

int maxim(int nod, llnode *act){
    if(act==NULL) return 0;
    else{
        int t,h;
        t=act->ari;
        if(nod==D[t]){
           h=Sa[t];
        }
        else h=Da[t];
        return max(h,maxim(nod,act->next));
    }
}

//Task 1&2
int main(){
    int N,maxmin,i,asig=0,tot;
    cin >> N;
    for(i=0;i<N;i++){
        cin >> P[i];
        cam[i]=(llnode*)malloc(sizeof(llnode));
        cam[i]->node=-1;
        cam[i]->ari=-1;
        cam[i]->next=NULL;
        sum[i]=-1;
    }
    for(i=0;i<N-1;i++){
        cin >> S[i] >> D[i];
        /*S[i]=i;
        D[i]=i+1;*/
        add(D[i],i,S[i]);
        add(S[i],i,D[i]);
    }
    //HERE THERE BE DRAGONS
    calcular(0,cam[0]);
    tot=sum[0];
    for(i=0;i<N-1;i++){
        if(sum[S[i]]>sum[D[i]]){
            Da[i]=sum[D[i]];
            Sa[i]=tot-Da[i];
        }
        else{
            Sa[i]=sum[S[i]];
            Da[i]=tot-Sa[i];
        }
    }
    for(i=0;i<N;i++){
        maximo[i]=maxim(i,cam[i]->next);
    }
    maxmin=maximo[0];
    for(i=1;i<N;i++){
        if(maximo[i]<maxmin){
            asig=i;
            maxmin=maximo[i];
        }
    }
    cout << asig;
    return 0;
}