Cod sursa(job #2799115)
| Utilizator |  Marius B mgnt |
Data | 12 noiembrie 2021 12:58:10 |
|---|---|---|---|
| Problema | Arbore | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 59.78 kb |
#include <cstddef>
#include <cstdint>
#include <vector>
#include <fstream>
#include <algorithm>
#include <limits>
uint32_t floor_square_root (uint32_t arg__n) {
/// Given n, it returns ⌊√n⌋.
if (0 == arg__n) {
return 0; }
/* Find k ∈ ℤ, so that (2ᵏ)² ≤ n < (2ᵏ⁺¹)², and initialize p = 2ᵏ. */ uint32_t as__p = 1; {
uint32_t as__q = as__p + as__p;
while (((as__q * as__q) <= arg__n) && ((as__q * as__q) != 0)) {
as__p = as__q;
as__q = as__p + as__p; }}
/* Find s ∈ ℤ so that 1 ≤ s and s² ≤ n < (s + 1)². */ uint32_t as__s = 0; {
uint32_t as__z = 0;
while (0 < as__p) {
as__z = as__s + as__p;
if ((as__z * as__z) <= arg__n) {
as__s = as__z; }
as__p /= 2; }}
/* Go! */
return as__s;
}
uint32_t ceiling_square_root (uint32_t arg__n) {
uint32_t const as__floor_sqrt = floor_square_root(arg__n);
return (as__floor_sqrt + (((as__floor_sqrt * as__floor_sqrt) < arg__n) ? 1 : 0));
}
uint32_t ceiling_quotient (uint32_t arg__divident, uint32_t arg__divisor) {
return ((arg__divident / arg__divisor) + (((arg__divident % arg__divisor) != 0) ? 1 : 0));
}
struct Edge {
uint32_t idm__u;
uint32_t idm__v;
void assign_from (uint32_t as__u, uint32_t as__v) noexcept {
idm__u = as__u; idm__v = as__v;
}
void assign_to (uint32_t & as__u, uint32_t & as__v) const noexcept {
as__u = idm__u; as__v = idm__v;
}
};
struct Operation {
uint32_t idm__code;
uint32_t idm__p;
uint32_t idm__s;
void assign_update (uint32_t arg__p, uint32_t arg__s) noexcept {
idm__code = 1; idm__p = arg__p; idm__s = arg__s;
}
void assign_query (uint32_t arg__s) noexcept {
idm__code = 2; idm__p = 0; idm__s = arg__s;
}
};
class FastBits {
std::vector<uint8_t> idm__bits;
public:
FastBits (void) {
std::vector<uint8_t> as__bits(ceiling_quotient(1000001, 8));
idm__bits.swap(as__bits);
}
void set_clear (void) {
std::fill(idm__bits.begin(), idm__bits.end(), 0);
}
bool contains (uint32_t arg__value) const {
return (((idm__bits.at(arg__value / 8)) & (1 << (arg__value % 8))) != 0);
}
void set_add (std::vector<uint32_t> const & arg__values, size_t arg__first, size_t arg__last) {
uint32_t as__value = 0;
for (size_t as__i = arg__first; arg__last >= as__i; ++as__i) {
as__value = arg__values.at(as__i);
idm__bits.at(as__value / 8) |= (1 << (as__value % 8)); }
}
void set_remove (std::vector<uint32_t> const & arg__values, size_t arg__first, size_t arg__last) {
uint32_t as__value = 0;
for (size_t as__i = arg__first; arg__last >= as__i; ++as__i) {
as__value = arg__values.at(as__i);
idm__bits.at(as__value / 8) &= (~(1 << (as__value % 8))); }
}
};
struct Problem {
size_t idm__n = 0;
size_t idm__m = 0;
uint32_t idm__block_size = 0;
uint32_t idm__block_count = 0;
std::vector<Edge> idm__edges_array;
std::vector<Operation> idm__operations_array;
std::vector<uint32_t> idm__adj_index;
std::vector<uint32_t> idm__adj_array;
std::vector<uint8_t> idm__visited;
std::vector<uint32_t> idm__nodes_numbering_first;
std::vector<uint32_t> idm__nodes_numbering_last;
std::vector<uint32_t> idm__nodes_numbering_inverse;
std::vector<uint32_t> idm__amount_element_array;
std::vector<uint32_t> idm__amount_block_array;
std::vector<FastBits> idm__amount_block_set;
};
struct DfsContext {
uint32_t idm__number = 0;
std::vector<uint8_t> * idm__visited = nullptr;
std::vector<uint32_t> * idm__adj_index = nullptr;
std::vector<uint32_t> * idm__adj_array = nullptr;
std::vector<uint32_t> * idm__nodes_numbering_first = nullptr;
std::vector<uint32_t> * idm__nodes_numbering_last = nullptr;
};
void dfs_number_nodes (DfsContext * arg__context, uint32_t arg__p, uint32_t arg__u) {
/// It is the DFS recursive routine doing the numbering.
/// Also reports invalid input, if it detects a cycle, which should not be found.
arg__context->idm__visited->at(arg__u) = 1;
arg__context->idm__nodes_numbering_first->at(arg__u) = arg__context->idm__number;
arg__context->idm__number += 1;
for (uint32_t as__pos = arg__context->idm__adj_index->at(0 + arg__u);
arg__context->idm__adj_index->at(1 + arg__u) > as__pos; ++as__pos) {
if (arg__context->idm__adj_array->at(as__pos) != arg__p) {
if (arg__context->idm__visited->at(arg__context->idm__adj_array->at(as__pos)) != 0) {
throw std::runtime_error("Invalid input."); }
dfs_number_nodes(arg__context, arg__u, arg__context->idm__adj_array->at(as__pos)); }}
arg__context->idm__nodes_numbering_last->at(arg__u) = arg__context->idm__number - 1;
}
void update (Problem & arg__problem, uint32_t arg__range_first, uint32_t arg__range_last, uint32_t arg__amount) {
/// It performs the update operation.
uint32_t const as__segment_first = 0;
uint32_t const as__segment_last = static_cast<uint32_t>(arg__problem.idm__n) - 1;
if ( !((as__segment_first <= arg__range_first) && (arg__range_first <= arg__range_last) &&
(arg__range_last <= as__segment_last)) ) {
throw std::logic_error("Incorrect program."); }
uint32_t const as__block_size = arg__problem.idm__block_size;
uint32_t const as__block_span = arg__problem.idm__block_size - 1;
std::vector<uint32_t> & as__amount_element_array = arg__problem.idm__amount_element_array;
std::vector<uint32_t> & as__amount_block_array = arg__problem.idm__amount_block_array;
std::vector<FastBits> & as__amount_block_set = arg__problem.idm__amount_block_set;
uint32_t as__block_first = as__segment_first; uint32_t as__block_last = 0; size_t as__block_number = 0;
uint32_t as__block_part_first = 0; uint32_t as__block_part_last = 0; uint32_t as__index = 0;
// Skip over the blocks that are not to be changed by the range update.
as__block_number = arg__range_first / as__block_size;
as__block_first = as__block_number * as__block_size;
// Update the first block intersecting partially with the range to update.
as__block_last = std::min(as__block_first + as__block_span, as__segment_last);
if ((as__block_first < arg__range_first) || (arg__range_last < as__block_last)) {
as__amount_block_set.at(as__block_number).set_remove(as__amount_element_array, as__block_first, as__block_last);
as__block_part_first = arg__range_first; as__block_part_last = std::min(arg__range_last, as__block_last);
for (as__index = as__block_part_first; as__block_part_last >= as__index; ++as__index) {
as__amount_element_array.at(as__index) += arg__amount; }
as__amount_block_set.at(as__block_number).set_add(as__amount_element_array, as__block_first, as__block_last);
as__block_first = as__block_last + 1; as__block_number += 1; }
// Update blocks entirely included in the range to update.
while ((as__block_first + as__block_span) <= arg__range_last) {
as__amount_block_array.at(as__block_number) += arg__amount;
as__block_first += as__block_size; as__block_number += 1; }
// Update the last remaining block, intersecting partially the range to update, if any.
if (as__block_first <= arg__range_last) {
as__block_last = std::min(as__block_first + as__block_span, as__segment_last);
as__amount_block_set.at(as__block_number).set_remove(as__amount_element_array, as__block_first, as__block_last);
as__block_part_first = as__block_first; as__block_part_last = arg__range_last;
for (as__index = as__block_part_first; as__block_part_last >= as__index; ++as__index) {
as__amount_element_array.at(as__index) += arg__amount; }
as__amount_block_set.at(as__block_number).set_add(as__amount_element_array, as__block_first, as__block_last); }
}
uint32_t query (Problem & arg__problem, uint32_t arg__amount) {
/// It peforms the query operation.
uint32_t const as__n = static_cast<uint32_t>(arg__problem.idm__n);
uint32_t const as__block_size = arg__problem.idm__block_size;
std::vector<uint32_t> & as__amount_element_array = arg__problem.idm__amount_element_array;
std::vector<uint32_t> & as__amount_block_array = arg__problem.idm__amount_block_array;
std::vector<FastBits> & as__amount_block_set = arg__problem.idm__amount_block_set;
uint32_t as__block_first = 0; uint32_t as__block_last = 0; size_t as__block_number = 0;
uint32_t as__block_amount = 0; uint32_t as__set_amount = 0; uint32_t as__index = 0;
while (as__block_first < as__n) {
as__block_last = std::min(as__block_first + (as__block_size - 1), as__n - 1);
as__block_amount = as__amount_block_array.at(as__block_number);
if (as__block_amount <= arg__amount) {
as__set_amount = arg__amount - as__block_amount;
if (as__amount_block_set.at(as__block_number).contains(as__set_amount)) {
for (as__index = as__block_first; as__block_last >= as__index; ++as__index) {
if (as__amount_element_array.at(as__index) == as__set_amount) {
return as__index; }}
throw std::logic_error("Incorrect program."); }}
as__block_first = as__block_last + 1; as__block_number += 1; }
return as__n;
}
void read_the_tree__read_the_operations_array__allocate_all_the_needed_memory (Problem & arg__problem) {
/// It reads the edges of the tree, it reads the operations array, and it allocates all needed memory.
std::ifstream as__is("arbore.in");
size_t as__n = 0; size_t as__m = 0;
as__is >> as__n >> as__m;
if ((1 > std::min(as__n, as__m)) || (100000 < std::max(as__n, as__m))) {
throw std::runtime_error("Invalid input."); }
uint32_t const as__block_size = ceiling_square_root(as__n);
uint32_t const as__block_count = ceiling_quotient(as__n, as__block_size);
std::vector<Edge> as__edges_array(as__n - 1);
std::vector<Operation> as__operations_array(as__m);
std::vector<uint32_t> as__adj_index(as__n + 1);
std::vector<uint32_t> as__adj_array(2 * (as__n - 1));
std::vector<uint8_t> as__visited(as__n);
std::vector<uint32_t> as__nodes_numbering_first(as__n);
std::vector<uint32_t> as__nodes_numbering_last(as__n);
std::vector<uint32_t> as__nodes_numbering_inverse(as__n);
std::vector<uint32_t> as__amount_element_array(as__n);
std::vector<uint32_t> as__amount_block_array(as__block_count);
std::vector<FastBits> as__amount_block_set(as__block_count);
size_t as__i = 0; uint32_t as__u = 0; uint32_t as__v = 0;
size_t as__e = 0; uint32_t as__s = 0; uint32_t as__p = 0;
for (as__i = 1; as__n > as__i; ++as__i) {
as__is >> as__u >> as__v;
if ((1 > std::min(as__u, as__v)) || (as__n < std::max(as__u, as__v))) {
throw std::runtime_error("Invalid input."); }
as__edges_array.at(as__i - 1).assign_from(as__u - 1, as__v - 1); }
for (as__i = 0; as__m > as__i; ++as__i) {
as__is >> as__e;
if ((1 != as__e) && (2 != as__e)) {
throw std::runtime_error("Invalid input."); }
if (1 == as__e) {
as__is >> as__p >> as__s;
if ((1 > as__p) || (as__n < as__p) || (1 > as__s) || (10 < as__s)) {
throw std::runtime_error("Invalid input."); }
as__operations_array.at(as__i).assign_update(as__p - 1, as__s); }
else {
as__is >> as__s;
if (1000000 < as__s) {
throw std::runtime_error("Invalid input."); }
as__operations_array.at(as__i).assign_query(as__s); }}
// Okay!
arg__problem.idm__n = as__n;
arg__problem.idm__m = as__m;
arg__problem.idm__block_size = as__block_size;
arg__problem.idm__block_count = as__block_count;
arg__problem.idm__edges_array.swap(as__edges_array);
arg__problem.idm__operations_array.swap(as__operations_array);
arg__problem.idm__adj_index.swap(as__adj_index);
arg__problem.idm__adj_array.swap(as__adj_array);
arg__problem.idm__visited.swap(as__visited);
arg__problem.idm__nodes_numbering_first.swap(as__nodes_numbering_first);
arg__problem.idm__nodes_numbering_last.swap(as__nodes_numbering_last);
arg__problem.idm__nodes_numbering_inverse.swap(as__nodes_numbering_inverse);
arg__problem.idm__amount_element_array.swap(as__amount_element_array);
arg__problem.idm__amount_block_array.swap(as__amount_block_array);
arg__problem.idm__amount_block_set.swap(as__amount_block_set);
}
void build_adjacency_list (Problem & arg__problem) {
size_t const as__n = arg__problem.idm__n;
std::vector<Edge> const & as__edges_array = arg__problem.idm__edges_array;
std::vector<uint32_t> & as__adj_index = arg__problem.idm__adj_index;
std::vector<uint32_t> & as__adj_array = arg__problem.idm__adj_array;
size_t as__i = 0; uint32_t as__u = 0; uint32_t as__v = 0;
uint32_t as__pos = 0; uint32_t as__outdeg = 0;
// Scan out degrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + as__n, 0);
for (as__i = 1; as__n > as__i; ++ as__i) {
as__edges_array.at(as__i - 1).assign_to(as__u, as__v);
as__adj_index.at(as__u) += 1;
as__adj_index.at(as__v) += 1; }
// Initialize adjacency lists first elements indices.
for (as__i = 0; as__n > as__i; ++as__i) {
as__outdeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__pos;
as__pos += as__outdeg; }
// Scan outgoing edges.
for (as__i = 1; as__n > as__i; ++ as__i) {
as__edges_array.at(as__i - 1).assign_to(as__u, as__v);
as__adj_array.at(as__adj_index.at(as__u)) = as__v;
as__adj_index.at(as__u) += 1;
as__adj_array.at(as__adj_index.at(as__v)) = as__u;
as__adj_index.at(as__v) += 1; }
// Scan out degrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + as__n, 0);
for (as__i = 1; as__n > as__i; ++ as__i) {
as__edges_array.at(as__i - 1).assign_to(as__u, as__v);
as__adj_index.at(as__u) += 1;
as__adj_index.at(as__v) += 1; }
// Initialize adjacency lists first elements indices.
as__pos = 0;
for (as__i = 0; as__n > as__i; ++as__i) {
as__outdeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__pos;
as__pos += as__outdeg; }
// Initialize last sentinel.
as__adj_index.at(as__n) = as__pos;
}
void index_the_nodes (Problem & arg__problem) {
/// It indexes the nodes of the tree so that each subtree is given consecutively integers, with DFS.
/// Each node is numbered less than any other node in its subtree.
/// Also we record the last node number in each subtree.
/// It validates the edges to be a tree.
size_t const as__n = arg__problem.idm__n;
std::vector<uint8_t> & as__visited = arg__problem.idm__visited;
std::vector<uint32_t> & as__adj_index = arg__problem.idm__adj_index;
std::vector<uint32_t> & as__adj_array = arg__problem.idm__adj_array;
std::vector<uint32_t> & as__nodes_numbering_first = arg__problem.idm__nodes_numbering_first;
std::vector<uint32_t> & as__nodes_numbering_last = arg__problem.idm__nodes_numbering_last;
std::vector<uint32_t> & as__nodes_numbering_inverse = arg__problem.idm__nodes_numbering_inverse;
std::fill(as__visited.begin(), as__visited.begin() + as__n, 0);
DfsContext as__ctx;
as__ctx.idm__number = 0;
as__ctx.idm__visited = &as__visited;
as__ctx.idm__adj_index = &as__adj_index;
as__ctx.idm__adj_array = &as__adj_array;
as__ctx.idm__nodes_numbering_first = &as__nodes_numbering_first;
as__ctx.idm__nodes_numbering_last = &as__nodes_numbering_last;
dfs_number_nodes(&as__ctx, 0, 0);
if (std::find(as__visited.begin(), as__visited.begin() + as__n, 0) != (as__visited.begin() + as__n)) {
throw std::runtime_error("Invalid input."); }
uint32_t as__i = 0;
for (as__i = 0; as__n > as__i; ++as__i) {
as__nodes_numbering_inverse.at(as__nodes_numbering_first.at(as__i)) = as__i; }
}
void prepare_for_operations (Problem & arg__problem) {
size_t const as__n = arg__problem.idm__n;
uint32_t const as__k = arg__problem.idm__block_count;
std::vector<uint32_t> & as__amount_element_array = arg__problem.idm__amount_element_array;
std::vector<uint32_t> & as__amount_block_array = arg__problem.idm__amount_block_array;
std::vector<FastBits> & as__amount_block_set = arg__problem.idm__amount_block_set;
std::fill(as__amount_element_array.begin(), as__amount_element_array.begin() + as__n, 0);
std::fill(as__amount_block_array.begin(), as__amount_block_array.begin() + as__k, 0);
uint32_t as__i = 0;
for (as__i = 0; as__k > as__i; ++as__i) {
as__amount_block_set.at(as__i).set_clear();
as__amount_block_set.at(as__i).set_add(as__amount_element_array, 0, 0); }
}
void perform_operations (Problem & arg__problem) {
/// It performs the operations, with the square root decomposition detailed by the official solution.
/// https://infoarena.ro/preoni-2006/finala/solutii (the official solution is here)
size_t const as__m = arg__problem.idm__m;
size_t const as__n = arg__problem.idm__n;
std::vector<Operation> & as__operations_array = arg__problem.idm__operations_array;
std::vector<uint32_t> & as__nodes_numbering_first = arg__problem.idm__nodes_numbering_first;
std::vector<uint32_t> & as__nodes_numbering_last = arg__problem.idm__nodes_numbering_last;
std::vector<uint32_t> & as__nodes_numbering_inverse = arg__problem.idm__nodes_numbering_inverse;
size_t as__i = 0; uint32_t as__code = 0; uint32_t as__p = 0; uint32_t as__s = 0;
uint32_t as__first = 0; uint32_t as__last = 0;
for (as__i = 0; as__m > as__i; ++as__i) {
as__code = as__operations_array.at(as__i).idm__code;
as__p = as__operations_array.at(as__i).idm__p;
as__s = as__operations_array.at(as__i).idm__s;
if (as__code == 1 /* update */) {
as__first = as__nodes_numbering_first.at(as__p);
as__last = as__nodes_numbering_last.at(as__p);
update(arg__problem, as__first, as__last, as__s);
continue; }
if (as__code == 2 /* query */) {
as__p = query(arg__problem, as__s);
as__operations_array.at(as__i).idm__p = ((as__p != as__n) ? as__nodes_numbering_inverse.at(as__p) : as__n);
continue; }
throw std::logic_error("Incorrect program."); }
}
void write_answers (Problem & arg__problem) {
/// It writes the answers.
std::ofstream as__os("arbore.out");
size_t const as__m = arg__problem.idm__m;
size_t const as__n = arg__problem.idm__n;
std::vector<Operation> const & as__operations_array = arg__problem.idm__operations_array;
uint32_t as__p = 0;
for (size_t as__i = 0; as__m > as__i; ++as__i) {
if (as__operations_array.at(as__i).idm__code == 2 /* Query */) {
as__p = as__operations_array.at(as__i).idm__p;
if (as__n != as__p) {
as__os << 1 + as__operations_array.at(as__i).idm__p /* The answer is YES! */ << '\n'; }
else {
as__os << "-1" /* The answer is NONE. */ "\n"; }}}
}
void demo (void) {
/// It does everything: read the input, solve the queries, write the answers.
Problem as__problem;
read_the_tree__read_the_operations_array__allocate_all_the_needed_memory (as__problem);
build_adjacency_list (as__problem);
index_the_nodes (as__problem);
prepare_for_operations (as__problem);
perform_operations (as__problem);
write_answers (as__problem);
}
int main (void) {
int status = 19;
try {
demo ();
status = 0; }
catch ( ... ) {
status = 13; }
return status;
}
