Submission #1245574

#TimeUsernameProblemLanguageResultExecution timeMemory
1245574msrivera1404Tree (IOI24_tree)C++20
Compilation error
0 ms0 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; }

Compilation message (stderr)

tree.cpp: In function 'void init(std::vector<int>, std::vector<int>)':
tree.cpp:22:3: error: 'adjency_list' was not declared in this scope; did you mean 'adjacency_list'?
   22 |   adjency_list.resize(n);
      |   ^~~~~~~~~~~~
      |   adjacency_list