Cod sursa(job #3149891)

Utilizator andrei1807Andrei andrei1807 Data 13 septembrie 2023 13:01:24
Problema Dosare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("dosare.in");
ofstream fout("dosare.out");

const int NMAX = 16003;

vector<int> g[NMAX];
int tata[NMAX], f[NMAX], dp[NMAX], c[NMAX];
bool vis[NMAX];


void sortare(vector<int>& v) {
    bool ok = false;
    int size = (int)v.size();
    while (!ok) {
        ok = true;
        for (int i = 0; i < size - 1; i++) {
            int c1 = (i + 1) * dp[v[i]], c2 = (i + 1) * dp[v[i + 1]];
            if (c1 > c2) {
                ok = false;
                int aux = v[i];
                v[i] = v[i + 1];
                v[i + 1] = aux;
            }
        }
    }
}

bool cmp(const int& a, const int& b) {
    return dp[a] > dp[b];
}

void dfs(const int& nod, const int& ind) {
    vis[nod] = true;

    dp[nod] = ind;

    bool frunza = true;
    int i = 0;
    for (auto fiu : g[nod]) {
        if (!vis[fiu]) {
            frunza = false;
            dfs(fiu, i);
            i++;
        }
    }

    if (frunza)
        return;

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

    i = 0;
    for (auto fiu : g[nod]) {
        dp[nod] += i * dp[fiu];
        i++;
    }
}

int res = 1;
void calc_cost(const int& nod, const int& cost) {
    vis[nod] = true;

    int i = 0;
    for (auto fiu : g[nod]) {
        res += f[fiu] * (cost + i + 1);
        //cout << fiu << ' ' << cost + i + 1<< '\n';

        calc_cost(fiu, cost + i + 1);

        i++;
    }
}

int main() {

    int n;
    fin >> n;
    for (int i = 2; i <= n; i++) {
        fin >> tata[i];
        g[tata[i]].push_back(i);
    }

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

    dfs(1, 0);

    memset(vis, 0, sizeof(vis));

    calc_cost(1, 1);

//    for (int i = 1; i <= n; i++)
//        cout << dp[i] << ' ';


    fout << res;

    return 0;
}