| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1245574 | msrivera1404 | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include "tree.h"
#include<bits/stdc++.h>
#define ll long long
#define first_val first
#define second_val second
#define new_line "\n"
using namespace std;
const ll INFINITY_VAL = 2e9;
const ll MOD_VAL = 998244353;
// Variables globales
int n;
vector<int> parent_nodes;
vector<int> vertex_weights;
vector<vector<int>> adjacency_list;
void init(std::vector<int> P, std::vector<int> W) {
parent_nodes = P;
vertex_weights = W;
n = (int)parent_nodes.size();
adjency_list.resize(n);
for(ll i=1; i<n; i++){
adjency_list[parent_nodes[i]].push_back(i);
}
}
// Función recursiva
// u: el vértice actual que se está procesando
// min_L: el límite inferior L
// max_R: el límite superior R
// Retorna: un par que contiene:
// - un par: {costo_total_subarbol, suma_coeficientes_subarbol}
// - un mapa: coeficientes_disponibles_para_decremento (peso_vertice -> cantidad_coeficientes)
pair<pair<ll, ll>, map<ll, ll>> calculate_subtree_optimal_cost(ll u, ll min_L, ll max_R) {
map<ll, ll> available_decrements_map;
ll current_subtree_sum_coeffs = 0;
ll current_subtree_cost = 0;
// Caso base: si el vértice actual 'u' es una hoja
if (adjacency_list[u].empty()) {
//C[i] = L
ll leaf_cost = vertex_weights[u] * min_L;
ll leaf_sum = min_L;
return {{leaf_cost, leaf_sum}, available_decrements_map};
} else {
for (auto child_v : adjacency_list[u]) {
auto child_result = calculate_subtree_optimal_cost(child_v, min_L, max_R);
// Acumula la suma de coeficientes y el costo de los subárboles de los hijos
current_subtree_sum_coeffs += child_result.first_val.second_val;
current_subtree_cost += child_result.first_val.first_val;
for (auto const& [weight_val, count] : child_result.second_val) {
available_decrements_map[weight_val] += count;
}
}
if (current_subtree_sum_coeffs > max_R) {
// Mientras la suma exceda R y haya coeficientes "baratos" (de hijos) disponibles para reducir,
// y el peso del nodo actual (u) no sea más barato que el coeficiente más barato de los hijos:
while (current_subtree_sum_coeffs > max_R &&
!available_decrements_map.empty() &&
vertex_weights[u] > available_decrements_map.begin()->first_val) {
ll decrement_amount = min(current_subtree_sum_coeffs - max_R, available_decrements_map.begin()->second_val);
current_subtree_sum_coeffs -= decrement_amount;
current_subtree_cost += decrement_amount * (available_decrements_map.begin()->first_val);
if (available_decrements_map.begin()->second_val == decrement_amount) {
available_decrements_map.erase(available_decrements_map.begin());
} else {
available_decrements_map[available_decrements_map.begin()->first_val] -= decrement_amount; // Reduce la cantidad
}
}
if (current_subtree_sum_coeffs > max_R) {//opcion mas barata
ll decrement_amount = current_subtree_sum_coeffs - max_R;
current_subtree_sum_coeffs -= decrement_amount; // Reduce la suma al límite R
current_subtree_cost += vertex_weights[u] * decrement_amount;
}
}
available_decrements_map[vertex_weights[u]] += (current_subtree_sum_coeffs - min_L);
ll capacity_for_parent = current_subtree_sum_coeffs - min_L;
map<ll, ll> final_available_decrements;
ll current_sum_added_to_parent_map = 0;
for (auto const& [weight_val, count] : available_decrements_map) {
if (current_sum_added_to_parent_map == capacity_for_parent) break;
ll add_amount = min(count, capacity_for_parent - current_sum_added_to_parent_map);
final_available_decrements[weight_val] += add_amount;
current_sum_added_to_parent_map += add_amount;
}
return {{current_subtree_cost, current_subtree_sum_coeffs}, final_available_decrements};
}
}
long long query(int L, int R) {
auto result = calculate_subtree_optimal_cost(0, L, R);
return result.first_val.first_val;
}