Cod sursa(job #718529)

Utilizator vendettaSalajan Razvan vendetta Data 20 martie 2012 21:11:47
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 16005

using namespace std;

ifstream f("dosare.in");
ofstream g("dosare.out");

int n, d[nmax], v[nmax];
vector<int> gf[nmax];
int accesari[nmax];//accesari[i] = nr, numarul de accesari pentru nodul i
int s;

void citeste(){

    f >> n;
    for(int i=2; i<=n; i++){
        int x;
        f >> x;
        gf[x].push_back(i);
    }

    for(int i=1; i<=n; i++) f >> v[i];

}


bool cmp(int a, int b){

    return d[a] > d[b];

}

void dfs_1(int nod){

    for(int i=0; i<gf[nod].size(); i++){
        int vc = gf[nod][i];
        dfs_1(vc);
        d[nod] += d[vc]*v[vc];
    }

    sort(gf[nod].begin(), gf[nod].end(), cmp);

}

void calcul(int nod){

    s += accesari[nod];

    for(int i=0; i<gf[nod].size(); i++){
        int vc = gf[nod][i];
        accesari[vc] = (accesari[nod] + i + 1) *v[vc];
        calcul(vc);
    }

}
/*
void sortare(int nod){

    for(int i=0; i<gf[nod].size(); i++){
        int vc = gf[nod][i];
        sortare(vc);
    }
    //sort(gf[nod].begin(), gf[nod].end(), cmp);

}
*/
void scrie(){
/*
    for(int i=1; i<=n; i++){
        for(int j=0; j<gf[i].size(); j++) g << gf[i][j] << " ";
        g << "\n";
    }
*/
    //for(int i=1; i<=n; i++) g << accesari[i] << "\n";
    g << s << "\n";
}

int main(){

    citeste();
    for(int i=1; i<=n; i++) d[i] = v[i], accesari[i] = 1;
    dfs_1(1);
    //sortare(1);
    calcul(1);
    scrie();

    f.close();
    g.close();

    return 0;

}