Cod sursa(job #2020946)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 12 septembrie 2017 13:52:44
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

#define MAXN 16000

long long total[1 + MAXN];
int acc[1 + MAXN], father[1 + MAXN];
std::vector <int> G[1 + MAXN];
long long sum = 0;

bool comp(int a, int b){
    if(total[a] <= total[b]) return 0;
    return 1;
}

void dfs(int node){
    total[node] = acc[node];
    for(int i = 0; i < G[node].size(); i++){
        dfs(G[node][i]);
        total[node] += total[G[node][i]];
    }
    std::sort(G[node].begin(), G[node].end(), comp);
    for(int i = 0; i < G[node].size(); i++){
        sum = sum + total[G[node][i]]*(1 + i);
    }
}

int main(){
    FILE*fi,*fo;
    fi = fopen("dosare.in","r");
    fo = fopen("dosare.out","w");

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 2; i <= n; i++){
        fscanf(fi,"%d", &father[i]);
        G[father[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++)
        fscanf(fi,"%d", &acc[i]);

    dfs(1);
    sum += total[1];
    /*for(int i = 1; i <= n; i++)
        printf("%d %d\n", i, total[i]);
    for(int i = 1; i <= n; i++){
        printf("%d     ", i);
        for(int j = 0; j < G[i].size(); j++)
            printf("%d ", G[i][j]);
        printf("\n");
    }*/
    fprintf(fo,"%lld", sum);
    fclose(fi);
    fclose(fo);
    return 0;
}