Submission #1132078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132078		aaaaaarroz	Tree (IOI24_tree)	C++20	0 / 100	2093 ms	29860 KiB

tree

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

vector<vector<int>> tree;
vector<int> weight;
vector<long long> dp;

void dfs(int node, int parent, vector<int>& L, vector<int>& R) {
    dp[node] = 0; // Inicializamos el costo del nodo
    for (int child : tree[node]) {
        if (child == parent) continue;
        dfs(child, node, L, R);
        dp[node] += dp[child];
    }
    // Ajustamos el rango de coeficientes para el nodo
    dp[node] = max(dp[node], (long long)L[node]);
    dp[node] = min(dp[node], (long long)R[node]);
    dp[node] *= weight[node]; // Agregamos el peso
}

void init(vector<int> P, vector<int> W) {
    int n = P.size();
    tree.assign(n, vector<int>());
    weight = W;
    dp.assign(n, 0);

    for (int i = 1; i < n; i++) {
        tree[P[i]].push_back(i);
        tree[i].push_back(P[i]);
    }
}

long long query(int L, int R) {
    vector<int> minL(weight.size(), L), maxR(weight.size(), R);
    dfs(0, -1, minL, maxR);
    return dp[0];
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19