Submission #1245856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245856		msrivera1404	Tree (IOI24_tree)	C++20	23 / 100	2098 ms	47520 KiB

tree

#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;

// 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();
  adjacency_list.resize(n);
  for(ll i=1; i<n; i++){
    adjacency_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;
}

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