#define GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE
#if defined(GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE) /* It is the folding section where the folding constructs are defined. */
#define GUVERN_PROGRAM__MACRO__FOLDING__BLOCK_SCOPE_BRACKETS__OPEN {
#define GUVERN_PROGRAM__MACRO__FOLDING__BLOCK_SCOPE_BRACKETS__CLOSE }
#define GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN GUVERN_PROGRAM__MACRO__FOLDING__BLOCK_SCOPE_BRACKETS__CLOSE
#define GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE GUVERN_PROGRAM__MACRO__FOLDING__BLOCK_SCOPE_BRACKETS__OPEN
#endif
#if defined(GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE) /* It is the folding section where the exit status values are defined, the bunch of them. */
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE 0
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE 1
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUTPUT_FILE 2
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR 3
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T 4
#define GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY 5
#endif
#if defined(GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE) /* It is the folding section where the headers are included, one by one, the lot of them. */
#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <inttypes.h>
#endif
#if defined(GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE) /* It is the folding section where the counting set is defined, on top of a segment tree. */
static size_t guvern_program__code__no_wraparound_addition_or_zero (size_t a, size_t b) {
/**
*** It returns the value a + b,
***
*** if the arithmetic sum of a and b, fits in a size_t variable,
***
*** otherwise it returns 0.
***
***
*** Such a routine is gold for carefully coding so that size_t + size_t used for determining a memory size to use with malloc does not suffer a wrap around.
***
*** Not really doing much in this program, but still it is more satisfying to code with the size_t wraparound possibility in sight.
**/
return (((SIZE_MAX - a) >= b) ? (a + b) : 0);
}
static size_t guvern_program__code__no_wraparound_multiplication_or_zero (size_t a, size_t b) {
/**
*** It returns the value a * b,
***
*** if a · b, the arithmetic product of a and b, fits in an size_t variable,
***
*** otherwise it returns 0.
***
***
***
*** Such a routine is gold for carefully coding so that size_t × size_t used for determining a memory size to use with malloc does not suffer a wrap around.
***
*** Not really doing much in this program, but still it is more satisfying to code with the size_t wraparound possibility in sight.
**/
return (((SIZE_MAX / b) >= a) ? (a * b) : 0);
}
static size_t guvern_program__code__ceiling_of_log_2 (size_t n) {
/**
*** Given n = 0, return 0; given n ∈ ℤ, 1 ≤ n, return ⌈log₂(n)⌉;
***
*** tertium non datur, since size_t stores unsigned integers.
***
***
***
*** Used to determine the stack size of the stack to be used for merge sort of an array of n elements.
***
**/
size_t result = 0;
if (0 == n) {
result = 0;
}
else {
size_t const one = 1;
size_t k = 0;
while ((n >> k) > 0) {
k += 1;
}
result = k + ((n > (one << k)) ? 1 : 0);
}
return result;
}
struct guvern_program__struct__counting_set {
/**
*** struct guvern_program__counting_set
***
*** • It is to be used as an opaque pointer, by the rest of the program, only the routines directly related to it need to know the data members in this struct.
***
*** • It is to be a segment tree plus O(1) data members useful with filtering out invalid inputs once the segment tree based counting set is fully initialized.
***
*** • It is to be a data structure representing a set with integer elements from 0 to one_past_the_last − 1, suporting insert(S, k), remove(S, k), and least_larger(S, k).
***
*** • The insert(k), and remove(k) are the usual insert, erase set operations.
***
*** • The least_larger(S, k) is the query operation returning min {x; x ∈ S ∪ {n}, k < x}, with n := one_past_the_last.
***
*** • Implementation achieves O(log(n)) time for insert(S, k) and remove(S, k), and least_larger(S, k), n := one_past_the_last.
***
***
*** • crude indicator function in that size_t is used for each element, instead of a single bit, so a crude approach, not too refined, but fine all the same
***
***
**/
size_t guvern_program__data_member__one_past_the_last; /** S ⊆ [0, one_past_the_last − 1] ∩ ℤ; S being the set encoded in the struct instance. **/
size_t * guvern_program__data_member__crude_indicator_function_array; /** crude_indicator_function[j] != 0 ⇔ j ∈ S, ∀ j ∈ ℤ, 0 ≤ j < one_past_the_last; not really needed **/
size_t guvern_program__data_member__segment_tree_size; /** the binary search tree, the total number of its segments. **/
size_t guvern_program__data_member__segment_tree_extent; /** the binary search tree, the span of its outermost segment, [0, 2ᵏ − 1] ∩ ℤ. **/
size_t * guvern_program__data_member__segment_tree_array; /** the binary indexed tree, used in the counting set, in the binary search **/
};
static int guvern_program__code__counting_set__acquire (size_t one_past_max_value, struct guvern_program__struct__counting_set * ( * the_counting_set_receptacle) ) {
/** It allocates all the memory needed for representing any set S ⊆ [0, one_past_max_value − 1] ∩ ℤ. */
/* Step is define and O(1) initialize a handful of variables local in the immediate enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
size_t exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
size_t const one_past_the_last = one_past_max_value;
struct guvern_program__struct__counting_set * the_counting_set_itself = NULL;
void ( * the_crude_indicator_function_array_itself) = NULL;
size_t the_segment_tree_its_size_itself = 0;
size_t the_segment_tree_its_extent_itself = 0;
void ( * the_segment_tree_array_itself ) = NULL;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is ensure that no wraparound may occur during the point update and range query operations below. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (1 > one_past_the_last) {
/* Segment trees are to be used for one_past_the_last at least one, in one type of extreme case. */
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
}
}
/* Step is allocate the counting set instance itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_bytes = sizeof(struct guvern_program__struct__counting_set);
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_counting_set_itself = p;
}
}
}
/* Step is allocate the crude indicator function array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = one_past_max_value;
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t));
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_crude_indicator_function_array_itself = p;
}
}
}
}
/* Step is allocate the segment tree array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t size_of_outermost_segment = 0;
size_t number_of_segments = 0;
/*
* Let n := one_past_the_last, determine g ∈ ℤ, 0 ≤ g, n − 1 ≤ 2ᵍ − 1, g minimum possible.
*
* n − 1 ≤ 2ᵍ − 1 ⇐⇒ n ≤ 2ᵍ, and after next loop, size_of_outermost_segment is to be 2ᵍ.
*
* 2ᵍ is the extent of the segment at the root of our segment tree.
*/
size_of_outermost_segment = 1;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (size_of_outermost_segment < one_past_the_last)) {
if ((SIZE_MAX - size_of_outermost_segment) >= size_of_outermost_segment) {
size_of_outermost_segment = size_of_outermost_segment + size_of_outermost_segment;
}
else {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/* 2ᵍ + 2ᵍ⁻¹ + … + 2² + 2¹ + 2⁰ = 2ᵍ + 2ᵍ − 1 = 2ᵍ⁺¹ − 1 is the size (number of nodes) of our segment tree.
*
* 2ᵍ⁺¹ − 1 is to be stored in number_of_segments.
*
*/
if ((SIZE_MAX - (size_of_outermost_segment - 1)) >= size_of_outermost_segment) {
number_of_segments = size_of_outermost_segment + (size_of_outermost_segment - 1);
}
else {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_segments;
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t));
/*
* Let there also be memory, if all the circumstances are favorable.
*/
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_segment_tree_its_size_itself = number_of_segments;
the_segment_tree_its_extent_itself = size_of_outermost_segment;
the_segment_tree_array_itself = p;
}
}
}
}
}
/* Step is publish the acquired resource, if any. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
the_counting_set_itself->guvern_program__data_member__one_past_the_last = one_past_the_last;
the_counting_set_itself->guvern_program__data_member__crude_indicator_function_array = the_crude_indicator_function_array_itself;
the_counting_set_itself->guvern_program__data_member__segment_tree_size = the_segment_tree_its_size_itself;
the_counting_set_itself->guvern_program__data_member__segment_tree_extent = the_segment_tree_its_extent_itself;
the_counting_set_itself->guvern_program__data_member__segment_tree_array = the_segment_tree_array_itself;
*the_counting_set_receptacle = the_counting_set_itself;
}
else {
if (NULL != the_segment_tree_array_itself) {
free(the_segment_tree_array_itself);
the_segment_tree_array_itself = NULL;
}
if (NULL != the_crude_indicator_function_array_itself) {
free(the_crude_indicator_function_array_itself);
the_crude_indicator_function_array_itself = NULL;
}
if (NULL != the_counting_set_itself) {
free(the_counting_set_itself);
the_counting_set_itself = NULL;
}
}
return exit_status;
}
}
static void guvern_program__code__counting_set__initialize_as_empty_set (struct guvern_program__struct__counting_set * counting_set) {
/** It operates the initialization S := ∅. */
size_t const one_past_the_last = counting_set->guvern_program__data_member__one_past_the_last;
size_t ( * const crude_indicator ) = counting_set->guvern_program__data_member__crude_indicator_function_array;
size_t const segment_size = counting_set->guvern_program__data_member__segment_tree_size;
size_t ( * const segment_tree ) = counting_set->guvern_program__data_member__segment_tree_array;
size_t index_J = 0;
index_J = 0;
while (one_past_the_last > index_J) {
crude_indicator[index_J] = 0;
index_J = index_J + 1;
}
index_J = 0;
while (segment_size > index_J) {
segment_tree[index_J] = 0;
index_J = index_J + 1;
}
}
static void guvern_program__code__segment_tree__update (struct guvern_program__struct__counting_set * counting_set, size_t point_in_segment, size_t amount_for_point) {
size_t ( * const all_the_segments ) = counting_set->guvern_program__data_member__segment_tree_array;
size_t current_segment__its_very_own_first_index = 0;
size_t current_segment__its_very_own_first_point = 0;
size_t current_segment__its_very_own_size = counting_set->guvern_program__data_member__segment_tree_size;
size_t current_segment__its_very_own_extent = counting_set->guvern_program__data_member__segment_tree_extent;
size_t half_extent = 0;
size_t middle_point = 0;
size_t half_size = 0;
/* _ The well known invariant is
* _
* _ _
* _ _ current_segment__its_very_own_first_index ≤ point_in_segment ≤ current_segment__its_very_own_first_index + (current_segment__its_very_own_extent − 1)
* _ _
*/
while (1 < current_segment__its_very_own_extent) {
all_the_segments[current_segment__its_very_own_first_index + (current_segment__its_very_own_size - 1)] += amount_for_point;
half_size = ((current_segment__its_very_own_size + 1) >> 1) - 1;
half_extent = (current_segment__its_very_own_extent >> 1);
middle_point = current_segment__its_very_own_first_point + half_extent;
if (middle_point <= point_in_segment) {
current_segment__its_very_own_first_index += half_size;
current_segment__its_very_own_first_point = middle_point;
}
else {
/* these two remain unchanged. */
}
current_segment__its_very_own_size = half_size;
current_segment__its_very_own_extent = half_extent;
}
/*
* Having reached this point in the program, in the variable current_segment__its_very_own_size, value 1 is stored.
*/
all_the_segments[current_segment__its_very_own_first_index] += amount_for_point;
}
static void guvern_program__code__counting_set__insert_value (struct guvern_program__struct__counting_set * counting_set, size_t value) {
/** It will operate the update S := S ∪ {v}, on condition v ∈ [0, one_past_max_value − 1] ∩ ℤ, counting_set be S, value be v.
***
*** • It is the set insert update: S := S ∪ {x}, on condition that 0 ≤ x ≤ N − 1, otherwise nothing changes, with N := counting_set->one_past_the_last, x := value.
**/
size_t const one_past_the_last = counting_set->guvern_program__data_member__one_past_the_last;
if (one_past_the_last <= value) {
/* One does nothing in such a case … */
}
else {
size_t ( * const indicator_function ) = counting_set->guvern_program__data_member__crude_indicator_function_array;
if (0 != indicator_function[value]) {
/* The value is already in the set, no further change to the present data structure is needed! */
}
else {
size_t const plus_one = 1;
guvern_program__code__segment_tree__update(counting_set, value, plus_one);
indicator_function[value] = /* set mark: */ plus_one;
}
}
}
static void guvern_program__code__counting_set__remove_value (struct guvern_program__struct__counting_set * counting_set, size_t value) {
/** It operates the update S := S ‒ {v}, counting_set be S, value be v.
***
*** • It is the set remove update: S := S − {x}, on condition that 0 ≤ x ≤ N − 1, otherwise nothing changes, with N := counting_set->one_past_the_last, x := value.
**/
size_t const one_past_the_last = counting_set->guvern_program__data_member__one_past_the_last;
if (one_past_the_last <= value) {
/* One does nothing in such a case … */
}
else {
size_t ( * const indicator_function ) = counting_set->guvern_program__data_member__crude_indicator_function_array;
if (0 == indicator_function[value]) {
/* The value is already not in the set, no further change to the present data structure is needed! */
}
else {
size_t const plus_one = 1;
size_t const zero = 0;
size_t const minus_one = (zero - plus_one);
guvern_program__code__segment_tree__update(counting_set, value, minus_one);
indicator_function[value] = /* clear mark: */ zero;
}
}
}
static size_t guvern_program__code__segment_tree__least_point_after (struct guvern_program__struct__counting_set * counting_set, size_t point_in_segment) {
/* Step is define and O(1) initialize a handful of variables local in the immediately enclosing lexical block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
size_t ( * const all_the_segments ) = counting_set->guvern_program__data_member__segment_tree_array;
/* candidus (white) → candidatus (white-robed) → candidate (early 17th century), supposedly */
size_t possibly_the_initial_segment__its_very_own_first_index = 0;
size_t possibly_the_initial_segment__its_very_own_first_point = 0;
size_t possibly_the_initial_segment__its_very_own_size = 0;
size_t possibly_the_initial_segment__its_very_own_extent = 0;
size_t current_segment__its_very_own_first_index = 0;
size_t current_segment__its_very_own_first_point = 0;
size_t current_segment__its_very_own_size = 0;
size_t current_segment__its_very_own_extent = 0;
size_t half_extent = 0;
size_t middle_point = 0;
size_t half_size = 0;
size_t least_point_after = 0;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is scan down to the degenerate segment containing point_in_segment, determining the largest initial segment containing the least point larger than point_in_segment. */ {
/* … determining such a segment, if any …
*
*
* _ current_segment__its_very_own_first_index: j
* _
* _ current_segment__its_very_own_first_point: b
* _
* _ current_segment__its_very_own_size: 2ᵏ − 1
* _
* _ current_segment__its_very_own_extent: 2ᵏ⁻¹
* _
* _ _ • possibly_the_initial_segment__* variables represent the segment [b, b + 2ᵏ⁻¹ − 1] ∩ ℤ, containing precisely (b + 2ᵏ⁻¹ − 1) − b + 1 = 2ᵏ⁻¹ points.
* _ _
* _ _ • this segment [b, b + 2ᵏ⁻¹ − 1] ∩ ℤ starts at b, and its index in the segment tree, which is simply a size_t array, is j.
* _ _
* _ _ • if k = 1, then [b, b + 2ᵏ⁻¹ − 1] ∩ ℤ is leaf in the tree representing a degenerate segment, a segment containing just one point, point or element.
* _ _
* _ _ • if k > 1, then
* _ _
* _ _ _ • [b, b + 2ᵏ⁻¹ − 1] has two nodes in the segment tree, segment [b, b + 2ᵏ⁻² − 1] ∩ ℤ and segment [b + 2ᵏ⁻², b + 2ᵏ⁻¹ − 1] ∩ ℤ;
* _ _ _
* _ _ _ • [j, j + (2ᵏ − 1) − 1] ∩ ℤ = ([j, j + (2ᵏ−¹ − 1) − 1] ∩ ℤ) ∪ ([j + (2ᵏ−¹ − 1), j + 2ᵏ − 2] ∩ ℤ] ∪ {j + 2ᵏ − 1}
* _ _ _
* _ _ _ • [j, j + (2ᵏ−¹ − 1) − 1] ∩ ℤ is the set of integers, each of which is an index of the subtree rooted at the segment [b, b + 2ᵏ⁻² − 1] ∩ ℤ.
* _ _ _
* _ _ _ • [j + 2ᵏ−¹ − 1, j + 2ᵏ − 2] ∩ ℤ is the set of integers, each such an index of the subtree rooted at the segment [b + 2ᵏ⁻², b + 2ᵏ⁻¹ − 2] ∩ ℤ.
* _
* _ the root is the segment [0, 0 + 2ᵍ − 1], g ∈ ℤ, 0 ≤ g, n − 1 ≤ 2ᵍ − 1, g minimum such possible integer, n is the number of nodes from the problem, 1 ≤ n ≤ 200 000.
* _
* _ 2ᵏ⁻¹ + 2ᵏ⁻² + … + 2² + 2¹ + 2⁰ = 2ᵏ − 1, (b + 2ᵏ⁻²) + (2ᵏ⁻² − 1) = b + 2ᵏ − 1 , j + (2ᵏ−¹ − 1) + 2ᵏ−¹ − 1 = j + 2ᵏ − 2, above.
* _
* _ … this summat recursive and synthetic description of the tree is what is behind the almost unreadable coding bellow …
*
*/
possibly_the_initial_segment__its_very_own_first_index = counting_set->guvern_program__data_member__segment_tree_size;
possibly_the_initial_segment__its_very_own_first_point = counting_set->guvern_program__data_member__segment_tree_extent;
possibly_the_initial_segment__its_very_own_size = counting_set->guvern_program__data_member__segment_tree_size;
possibly_the_initial_segment__its_very_own_extent = counting_set->guvern_program__data_member__segment_tree_extent;
current_segment__its_very_own_first_index = 0;
current_segment__its_very_own_first_point = 0;
current_segment__its_very_own_size = counting_set->guvern_program__data_member__segment_tree_size;
current_segment__its_very_own_extent = counting_set->guvern_program__data_member__segment_tree_extent;
while (1 < current_segment__its_very_own_extent) {
half_size = ((current_segment__its_very_own_size + 1) >> 1) - 1;
half_extent = (current_segment__its_very_own_extent >> 1);
middle_point = current_segment__its_very_own_first_point + half_extent;
if (middle_point <= point_in_segment) {
current_segment__its_very_own_first_index += half_size;
current_segment__its_very_own_first_point = middle_point;
}
else {
if (0 < all_the_segments[current_segment__its_very_own_first_index + current_segment__its_very_own_size - 2]) {
possibly_the_initial_segment__its_very_own_first_index = current_segment__its_very_own_first_index + half_size;
possibly_the_initial_segment__its_very_own_first_point = middle_point;
possibly_the_initial_segment__its_very_own_size = half_size;
possibly_the_initial_segment__its_very_own_extent = half_extent;
}
}
current_segment__its_very_own_size = half_size;
current_segment__its_very_own_extent = half_extent;
}
}
/* Step is scan down from the initial segment containing the least point larger than point_in_segment, when any such was determined, that is, determining least_point_after. */ {
if (counting_set->guvern_program__data_member__segment_tree_extent <= possibly_the_initial_segment__its_very_own_first_point) {
least_point_after = counting_set->guvern_program__data_member__segment_tree_extent;
}
else {
current_segment__its_very_own_first_index = possibly_the_initial_segment__its_very_own_first_index;
current_segment__its_very_own_first_point = possibly_the_initial_segment__its_very_own_first_point;
current_segment__its_very_own_size = possibly_the_initial_segment__its_very_own_size;
current_segment__its_very_own_extent = possibly_the_initial_segment__its_very_own_extent;
while (1 < current_segment__its_very_own_size) {
half_size = ((current_segment__its_very_own_size + 1) >> 1) - 1;
half_extent = (current_segment__its_very_own_extent >> 1);
middle_point = current_segment__its_very_own_first_point + half_extent;
if (0 < all_the_segments[current_segment__its_very_own_first_index + (half_size - 1)]) {
/* One keeps, in this case, the first index and the first point, unchanged. */
}
else {
current_segment__its_very_own_first_index += half_size;
current_segment__its_very_own_first_point = middle_point;
}
current_segment__its_very_own_size = half_size;
current_segment__its_very_own_extent = half_extent;
}
least_point_after = current_segment__its_very_own_first_point;
}
return least_point_after;
}
}
static size_t guvern_program__code__counting_set__query_least_larger_value (struct guvern_program__struct__counting_set * counting_set, size_t given_value) {
/** It answers the query x := min {w; w ∈ S ∪ {one_past_max_value}, v < w}, counting_set be S, value be v, v be less than one_past_the_last.
***
***
*** It is the set query least larger value query: y := min {v | v ∈ S ∪ {n}, x < v}, with n := counting_set->one_past_the_last, x := given_value, O(n·log(n)) time …
***
***
*** If one_past_the_last ≤ given_value, then the returned value is invariably one_past_the_last; sorta, kinda the junk in, junk out approach.
***
***/
size_t const one_past_the_last = counting_set->guvern_program__data_member__one_past_the_last;
size_t least_larger_value = 0;
if (one_past_the_last <= given_value) {
least_larger_value = one_past_the_last;
}
else {
size_t segment_tree_result = 0;
segment_tree_result = guvern_program__code__segment_tree__least_point_after(counting_set, given_value);
least_larger_value = (one_past_the_last <= segment_tree_result) ? one_past_the_last : segment_tree_result;
}
return least_larger_value;
}
static void guvern_program__code__counting_set__release (struct guvern_program__struct__counting_set * counting_set) {
/** It gives back the once acquired memory. */
free(counting_set->guvern_program__data_member__segment_tree_array);
counting_set->guvern_program__data_member__segment_tree_array = NULL;
counting_set->guvern_program__data_member__segment_tree_size = 0; /* forget about it … */
free(counting_set->guvern_program__data_member__crude_indicator_function_array);
counting_set->guvern_program__data_member__crude_indicator_function_array = NULL;
counting_set->guvern_program__data_member__one_past_the_last = 0;
free(counting_set);
}
#endif
#if defined(GUVERN_PROGRAM__MACRO__FOLDING__FOLD_SCOPE) /* It is the folding section where the the problem data and its solving routines are defined. */
struct guvern_program__struct__node_and_its_value {
/** A pair, each node alongside its value. */
size_t guvern_program__data_member__the_node_itself;
/**
* Any node representing one minister from the problem statement.
*/
int32_t guvern_program__data_member__the_value_itself;
/**
* The cooperation degree, of the respective minister, with the secret services, from the problem statement,
*
* an integer which may be any element of the set [‒10⁹, +10⁹] ∩ ℤ; [‒10⁹, +10⁹] ∩ ℤ ⊂ int32_t.
*/
};
struct guvern_program__struct__dfs_stack_frame {
/** A stack frame struct for doing depth first search. */
size_t guvern_program__data_member__node_x;
/** The node itself. */
size_t guvern_program__data_member__neighbour_j;
/** A position in the list of neighbours of node_x, an index. */
};
struct guvern_program__struct__merge_sort_stack_frame {
/** A stack frame for normalizing the node values. */
size_t guvern_program__data_member__index_begin;
/** the B value, where [B, e) is the current slice to sort. **/
size_t guvern_program__data_member__index_end;
/** the E value, where [B, e) is the current slice to sort. **/
size_t guvern_program__data_member__index_subproblem;
/** which subproblem is next to solve: first half, second half, merge **/
};
struct guvern_program__struct__program_data {
/** All the objects used by the top level routines.
*
* • The objects that may have been discarded at the end of the input reading stage, at the end.
*
* ‣ At the end, because this way it is a good exercise on beeing aware of what may be dropped.
*
* ‣ Dropped because no longer used by the remaining of the processing to come.
*
* ‣ Kept and not dropped, because still in the given memory bounds, and because it is nice.
*
* ‣ It is nice to keep these, considering that the program may be initially buggy.
*
* ‣ If the program is buggy, simply looking at the data may reveal what went wrong.
*
* • Input and output FILE objects are kept, trying to achieve perfect paranthetic resource acquisition and relinquishing.
*
* ‣ Give everything back in reverse order of how everything was acquired.
*
* ‣ Acquisition in this program is through fopen(), and malloc(); relinquishing is through free(), and fclose().
*
* ‣ fscanf() may have its own acquisition and relinquishing, inside, and hopefully is neatly acquired and relinquished with the same approach.
*
* ‣ fscanf() is mentioned, because it is used in this program; possibly, that would be all, resource wise.
*/
FILE * guvern_program__data_member__input_file;
/** it gives us access to the contents of the input file */
FILE * guvern_program__data_member__output_file;
/** it gives us a way to write contents into the output file */
size_t guvern_program__data_member__number_of_nodes;
/** graph representation, part 1 of 3: the number of nodes */
size_t * guvern_program__data_member__neighbours_lists_array;
/** graph representation, part 2 of 3: the adjacency lists array */
size_t * guvern_program__data_member__neighbours_begin_array;
/** graph representation, part 3 of 3: the first neighbour index */
struct guvern_program__struct__dfs_stack_frame * guvern_program__data_member__dfs_stack_array;
/** the depth first stack, for a change let’s not explicitly recurse */
struct guvern_program__struct__counting_set * guvern_program__data_member__counting_set;
/** the counting set, providing the query least larger value query operation! */
size_t ( * guvern_program__data_member__edges_array)[2];
/** the edges array, number_of_nodes − 1 of them. */
size_t * guvern_program__data_member__dfs_parent_array;
/** the parent array, each node has one, root’s is root itself. */
struct guvern_program__struct__node_and_its_value * guvern_program__data_member__node_values_merge_array;
/**
* the nodes and their value, the merge array, the merge from merge sort.
*/
struct guvern_program__struct__node_and_its_value * guvern_program__data_member__node_values_sort_array;
/**
* the nodes and their value, the sort array, the merge from merge sort.
*/
struct guvern_program__struct__merge_sort_stack_frame ( * guvern_program__data_member__merge_sort_stack_array);
/**
* ⌈log₂(n)⌉ call stack frames, with n := number_of_nodes,
*
* to merge sort the node values,
*
* to rank the nodes by the position of their values,
*
* in the ascendently sorted list of node values.
*/
size_t * guvern_program__data_member__node_rank_array;
/**
* for each node, its rank: low rank lower cooperation,, high rank, higher cooperation.
*/
size_t * guvern_program__data_member__rank_node_array;
/**
* for each rank, its node.
*/
size_t * guvern_program__data_member__sink_cache_array;
/**
* sink_cache_array[x], a value cached for node x.
*/
size_t * guvern_program__data_member__snapshot_contribution_array;
/**
* snapshot_contribution_array[x] is to be … a snapshot value, for a better word; to be revisited.
*
*/
size_t * guvern_program__data_member__maximum_contribution_array;
/**
* maximum_contribution_array[x] is to be the maximum possible contribution from node x, possibly even accounted in the answer.
*
*
*/
size_t guvern_program__data_member__the_answer;
/**
* The number to go into the output file, that simple!
*
*/
};
static int guvern_program__code__read_input__part_1 (struct guvern_program__struct__program_data * * program_data) {
/** Allocates all the data, in one fell swoop.
***
*** • It opens the input file.
***
*** • It opens the output file.
***
*** • It reads the input: its size, allocating all the needed memory.
***
*** ‣ The size of the input is, in this case, the number of nodes.
***
*** • It validates that the number of nodes is in the bounds given in problem’s constraints.
***
*** • It leaves the input_file pointing right after where the number of nodes was in the input file.
***
*** • It allocates the various arrays to use later on for solving the problem.
***
*** • It either passes the baton, when all was fine, or deallocates the arrays and closes the files, on error.
**/
/* Step is define and O(1) initialize a handful of variables local to the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
size_t exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
void * the_program_data_itself = NULL;
FILE * input_file = NULL;
FILE * output_file = NULL;
size_t number_of_nodes = 0;
void * neighbours_lists_array = NULL;
void * neighbours_begin_array = NULL;
void * dfs_stack_array = NULL;
struct guvern_program__struct__counting_set * the_counting_set_itself = NULL;
void * dfs_parent_array = NULL;
void * edges_array = NULL;
void * the_node_values_merge_array_itself = NULL;
void * the_node_values_sort_array_itself = NULL;
void * the_merge_sort_stack_array_itself = NULL;
void * the_node_rank_array_itself = NULL;
void * the_rank_node_array_itself = NULL;
void * the_sink_cache_array_itself = NULL;
void * the_snapshot_contribution_array_itself = NULL;
void * the_maximum_contribution_array_itself = NULL;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is allocate the program data itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_bytes = sizeof(struct guvern_program__struct__program_data);
void ( * const p ) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_program_data_itself = p;
}
}
}
/* Step is open the input file. */ {
FILE * f = NULL;
f = fopen("guvern.in", "r");
if (NULL == f) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
input_file = f;
}
}
/* Step is open the output file. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
FILE * g = NULL;
g = fopen("guvern.out", "w");
if (NULL == g) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUTPUT_FILE;
}
else {
output_file = g;
}
}
}
/* Step is scan the number of nodes. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t num_nodes = 0;
int s_code = -1;
s_code = fscanf(input_file, "%zu", &num_nodes);
if (1 != s_code) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
if ((1 > num_nodes) || (200000 < num_nodes)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
number_of_nodes = num_nodes;
}
}
}
}
/* Step is increase number of nodes, by +1, to extend later on, the input given tree, with one auxiliary node. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t num_nodes = 0;
num_nodes = guvern_program__code__no_wraparound_addition_or_zero(number_of_nodes, 1);
if (0 == num_nodes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
number_of_nodes = num_nodes;
}
}
}
/* Step is allocate the neighbours lists array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = 0;
number_of_elements = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_nodes - 1, 2);
if ((0 == number_of_elements) && (1 != number_of_nodes)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
size_t number_of_bytes = 0;
number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t));
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void * p = NULL;
p = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
neighbours_lists_array = p;
}
}
}
}
}
/* Step is allocate the neighbours begin array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t number_of_elements = 0;
number_of_elements = guvern_program__code__no_wraparound_addition_or_zero(number_of_nodes, 1);
if (0 == number_of_elements) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
size_t number_of_bytes = 0;
number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t));
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p ) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
neighbours_begin_array = p;
}
}
}
}
}
/* Step is allocate the depth first search stack array . */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes; /* malloc(0) is … defined, it should not be causing any trouble */
size_t const element_byte_size = sizeof(struct guvern_program__struct__dfs_stack_frame);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void * const p = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
dfs_stack_array = p;
}
}
}
}
/* Step is allocate the counting set itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int exit_status_too = guvern_program__code__counting_set__acquire(number_of_nodes, &the_counting_set_itself);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
else {
if (NULL == the_counting_set_itself) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
else {
/* the_counting_set_itself was just initialized from NULL, to a memory address at which there is the counting set object. */
}
}
}
}
/* Step is allocate the edges array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes - 1;
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t[2]));
if ((0 == number_of_bytes) && (0 != number_of_elements)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p ) = malloc(number_of_bytes);
if ((NULL == p) && (0 != number_of_bytes)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
edges_array = p;
}
}
}
}
/* Step is allocate the parent array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, sizeof(size_t));
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p ) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
dfs_parent_array = p;
}
}
}
}
/* Step is allocate the node values merge array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(struct guvern_program__struct__node_and_its_value);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_node_values_merge_array_itself = p;
}
}
}
}
/* Step is allocate the node values sort array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(struct guvern_program__struct__node_and_its_value);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_node_values_sort_array_itself = p;
}
}
}
}
/* Step is allocate the merge sort stack array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = guvern_program__code__ceiling_of_log_2(number_of_nodes);
size_t const element_byte_size = sizeof(struct guvern_program__struct__merge_sort_stack_frame);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p ) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_merge_sort_stack_array_itself = p;
}
}
}
}
/* Step is allocate the node rank array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(size_t);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_node_rank_array_itself = p;
}
}
}
}
/* Step is allocate the rank node array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(size_t);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_rank_node_array_itself = p;
}
}
}
}
/* Step is allocate the sink cache array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(size_t);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const p) = malloc(number_of_bytes);
if (NULL == p) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_sink_cache_array_itself = p;
}
}
}
}
/* Step is allocate the snapshot contributor array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_size_in_bytes = sizeof(size_t);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_size_in_bytes);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const allocated_storage ) = malloc(number_of_bytes);
if (NULL == allocated_storage) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_snapshot_contribution_array_itself = allocated_storage;
}
}
}
}
/* Step is allocate the maximum contribution array itself. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const number_of_elements = number_of_nodes;
size_t const element_byte_size = sizeof(size_t);
size_t const number_of_bytes = guvern_program__code__no_wraparound_multiplication_or_zero(number_of_elements, element_byte_size);
if (0 == number_of_bytes) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
else {
void ( * const allocated_storage) = malloc(number_of_bytes);
if (NULL == allocated_storage) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUT_OF_MEMORY;
}
else {
the_maximum_contribution_array_itself = allocated_storage;
}
}
}
}
/* Step is return the exit status, publishing the acquired resource or disposing of all the acquired resources. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
struct guvern_program__struct__program_data * program_data_itself = the_program_data_itself;
program_data_itself->guvern_program__data_member__input_file = input_file;
program_data_itself->guvern_program__data_member__output_file = output_file;
program_data_itself->guvern_program__data_member__number_of_nodes = number_of_nodes;
program_data_itself->guvern_program__data_member__neighbours_lists_array = neighbours_lists_array;
program_data_itself->guvern_program__data_member__neighbours_begin_array = neighbours_begin_array;
program_data_itself->guvern_program__data_member__dfs_stack_array = dfs_stack_array;
program_data_itself->guvern_program__data_member__counting_set = the_counting_set_itself;
program_data_itself->guvern_program__data_member__edges_array = edges_array;
program_data_itself->guvern_program__data_member__dfs_parent_array = dfs_parent_array;
program_data_itself->guvern_program__data_member__node_values_merge_array = the_node_values_merge_array_itself;
program_data_itself->guvern_program__data_member__node_values_sort_array = the_node_values_sort_array_itself;
program_data_itself->guvern_program__data_member__merge_sort_stack_array = the_merge_sort_stack_array_itself;
program_data_itself->guvern_program__data_member__node_rank_array = the_node_rank_array_itself;
program_data_itself->guvern_program__data_member__rank_node_array = the_rank_node_array_itself;
program_data_itself->guvern_program__data_member__sink_cache_array = the_sink_cache_array_itself;
program_data_itself->guvern_program__data_member__snapshot_contribution_array = the_snapshot_contribution_array_itself;
program_data_itself->guvern_program__data_member__maximum_contribution_array = the_maximum_contribution_array_itself;
program_data_itself->guvern_program__data_member__the_answer = 0; /* not yet known … */
*program_data = program_data_itself;
}
else {
if (NULL != the_maximum_contribution_array_itself) {
free(the_maximum_contribution_array_itself);
the_maximum_contribution_array_itself = NULL;
}
if (NULL != the_snapshot_contribution_array_itself) {
free(the_snapshot_contribution_array_itself);
the_snapshot_contribution_array_itself = NULL;
}
if (NULL != the_sink_cache_array_itself) {
free(the_sink_cache_array_itself);
the_sink_cache_array_itself = NULL;
}
if (NULL != the_rank_node_array_itself) {
free(the_rank_node_array_itself);
the_rank_node_array_itself = NULL;
}
if (NULL != the_node_rank_array_itself) {
free(the_node_rank_array_itself);
the_node_rank_array_itself = NULL;
}
if (NULL != the_merge_sort_stack_array_itself) {
free(the_merge_sort_stack_array_itself);
the_merge_sort_stack_array_itself = NULL;
}
if (NULL != the_node_values_sort_array_itself) {
free(the_node_values_sort_array_itself);
the_node_values_sort_array_itself = NULL;
}
if (NULL != the_node_values_merge_array_itself) {
free(the_node_values_merge_array_itself);
the_node_values_merge_array_itself = NULL;
}
if (NULL != dfs_parent_array) {
free(dfs_parent_array);
dfs_parent_array = NULL;
}
if (NULL != edges_array) {
free(edges_array);
edges_array = NULL;
}
if (NULL != the_counting_set_itself) {
guvern_program__code__counting_set__release(the_counting_set_itself);
the_counting_set_itself = NULL;
}
if (NULL != dfs_stack_array) {
free(dfs_stack_array);
dfs_stack_array = NULL;
}
if (NULL != neighbours_begin_array) {
free(neighbours_begin_array);
neighbours_begin_array = NULL;
}
if (NULL != neighbours_lists_array) {
free(neighbours_lists_array);
neighbours_lists_array = NULL;
}
if (NULL != output_file) {
int c_code = -1;
c_code = fclose(output_file);
output_file = NULL;
if (0 != c_code) {
perror("Could not close the output file.");
}
}
if (NULL != input_file) {
int c_code = -1;
c_code = fclose(input_file);
input_file = NULL;
if (0 != c_code) {
perror("Could not close the input file.");
}
}
if (NULL != the_program_data_itself) {
free(the_program_data_itself);
the_program_data_itself = NULL;
}
}
return exit_status;
}
}
static int guvern_program__code__read_input__part_2 (struct guvern_program__struct__program_data * program_data) {
/** Reads, validates, and initializes the tree.
***
*** • It reads the tree like data, a list of n − 1 edges, where n is the number of nodes.
***
*** • It stores the n − 1 edges into the neighbours_list_array array of size 2·(n − 1).
***
*** ‣ The neighbours of node x, immediately before the neighbours of node x + 1, x ← 0 … n − 2.
***
*** • It stores in neighbours_begin_array[x] the position in neighbours_list_array, from where neighbours of node x were stored, x ← 0 … n − 1.
***
*** • It stores in neighbours_begin_array[n] a value so that neighbours_begin_array[(n − 1) + 1] − 1 is the last position of a neighbour of node n − 1.
***
*** • It validates that indeed the tree like data is really a tree.
***
*** ‣ To do this validation, it uses the neighbours_lists_array and neighbours_begin_array adjacency lists representation of the read graph.
***
*** ‣ While validating, it also initializes the parent_array, the dfs_number_self_array arrays, the dfs_number_last_array arrays.
***
*** ‣ It leaves the dfs_stack_array with default values in each one of its so called frames, facilitating debugging if somehow the program happens to be not okay.
**/
/* Step is define and O(1) initialize a handful of variables local to the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
size_t exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
size_t const number_of_nodes = program_data->guvern_program__data_member__number_of_nodes;
FILE ( * const input_file) = program_data->guvern_program__data_member__input_file;
size_t ( * const edges_array)[2] = program_data->guvern_program__data_member__edges_array;
size_t ( * const neighbours_lists_array ) = program_data->guvern_program__data_member__neighbours_lists_array;
size_t ( * const neighbours_begin_array ) = program_data->guvern_program__data_member__neighbours_begin_array;
size_t ( * const dfs_parent_array ) = program_data->guvern_program__data_member__dfs_parent_array;
struct guvern_program__struct__dfs_stack_frame ( * const dfs_stack_array ) = program_data->guvern_program__data_member__dfs_stack_array;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is it reads the tree like data from the input file. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const num_nodes = number_of_nodes - 1;
size_t const index_of_edge_x = 0;
size_t const index_of_edge_y = 1;
size_t number_of_edges = number_of_nodes - 1;
size_t edge_index = 0;
size_t edge_x = 0;
size_t edge_y = 0;
int s_code = 0;
edge_index = 0;
edges_array[edge_index][index_of_edge_x] = 0;
edges_array[edge_index][index_of_edge_y] = 1;
edge_index += 1;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (number_of_edges > edge_index)) {
s_code = fscanf(input_file, "%zu %zu", &edge_x, &edge_y);
if (2 != s_code) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
if ((edge_x < 1) || (num_nodes < edge_x) || (edge_y < 1) || (num_nodes < edge_y)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
if (edge_x == edge_y) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
edges_array[edge_index][index_of_edge_x] = edge_x;
edges_array[edge_index][index_of_edge_y] = edge_y;
edge_index += 1;
}
}
}
}
}
}
/* Step is bootstrap the neighbours lists array graph representation. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/* Step is for each node, count the number of its neighbours, or, more concise, its degree. */ {
size_t node_x = 0;
size_t const index_of_edge_x = 0;
size_t const index_of_edge_y = 1;
size_t const number_of_edges = number_of_nodes - 1;
size_t edge_index = 0;
size_t edge_x = 0;
size_t edge_y = 0;
node_x = 0;
while (number_of_nodes > node_x) {
neighbours_begin_array[node_x] = 0;
node_x += 1;
}
edge_index = 0;
while (number_of_edges > edge_index) {
edge_x = edges_array[edge_index][index_of_edge_x];
edge_y = edges_array[edge_index][index_of_edge_y];
neighbours_begin_array[edge_x] += 1;
neighbours_begin_array[edge_y] += 1;
edge_index += 1;
}
}
/* Step is compute the position of the first neighbour, for each node x, knowing already degree[y], for all nodes y. */ {
size_t posn_x = 0;
size_t next_p = 0;
size_t node_x = 0;
while (number_of_nodes > node_x) {
next_p = posn_x + neighbours_begin_array[node_x];
neighbours_begin_array[node_x] = posn_x;
posn_x = next_p;
node_x += 1;
}
}
/* Step is for each edge, lay each one of its two endpoints in the neighbours lists of the other of the two endpoints. */ {
size_t const index_of_edge_x = 0;
size_t const index_of_edge_y = 1;
size_t const number_of_edges = number_of_nodes - 1;
size_t edge_index = 0;
size_t edge_x = 0;
size_t edge_y = 0;
edge_index = 0;
while (number_of_edges > edge_index) {
edge_x = edges_array[edge_index][index_of_edge_x];
edge_y = edges_array[edge_index][index_of_edge_y];
neighbours_lists_array[neighbours_begin_array[edge_x]] = edge_y;
neighbours_begin_array[edge_x] += 1;
neighbours_lists_array[neighbours_begin_array[edge_y]] = edge_x;
neighbours_begin_array[edge_y] += 1;
edge_index += 1;
}
}
/* Step is for each node, count the number of its neighbours, or, more concise, its degree, once more and again. */ {
size_t node_x = 0;
size_t const index_of_edge_x = 0;
size_t const index_of_edge_y = 1;
size_t const number_of_edges = number_of_nodes - 1;
size_t edge_index = 0;
size_t edge_x = 0;
size_t edge_y = 0;
node_x = 0;
while (number_of_nodes > node_x) {
neighbours_begin_array[node_x] = 0;
node_x += 1;
}
edge_index = 0;
while (number_of_edges > edge_index) {
edge_x = edges_array[edge_index][index_of_edge_x];
edge_y = edges_array[edge_index][index_of_edge_y];
neighbours_begin_array[edge_x] += 1;
neighbours_begin_array[edge_y] += 1;
edge_index += 1;
}
}
/* Step is for each node, and a final sentinel, determine the position in the neighbours lists array from where its neighbours were layed. */ {
size_t posn_x = 0;
size_t next_p = 0;
size_t node_x = 0;
while (number_of_nodes > node_x) {
next_p = posn_x + neighbours_begin_array[node_x];
neighbours_begin_array[node_x] = posn_x;
posn_x = next_p;
node_x += 1;
}
neighbours_begin_array[number_of_nodes] = posn_x; /* the sentinel, itself */
}
}
}
/* Step is it validates that indeed the tree like data is a tree, initializing the parent and the dfs number arrays. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t const neighbours_sentinel = (number_of_nodes - 1) * 2;
/**
* (number_of_nodes - 1) * 2 is ∑ j ← 0 … number_of_nodes ∷ |the set of neighbours of node x|,
*
* by the famous hand shaking lemma, and by the number of edges in a tree.
*
* https://en.wikipedia.org/wiki/Handshaking_lemma
*
* https://en.wikipedia.org/wiki/Tree_(graph_theory)
*/
size_t current_dfs_number = 0;
size_t stack_size = 0;
size_t const tree_root = 0;
size_t node_x = 0;
size_t top_node = 0;
size_t n_index = 0;
size_t neighbour = 0;
size_t parent_node = 0;
node_x = 0;
while (number_of_nodes > node_x) {
dfs_parent_array[node_x] = number_of_nodes;
node_x += 1;
}
stack_size = 0;
while (number_of_nodes > stack_size) {
dfs_stack_array[stack_size].guvern_program__data_member__node_x = number_of_nodes;
dfs_stack_array[stack_size].guvern_program__data_member__neighbour_j = neighbours_sentinel;
stack_size += 1;
}
stack_size = 1;
dfs_parent_array[tree_root] = tree_root;
top_node = tree_root;
dfs_stack_array[stack_size - 1].guvern_program__data_member__node_x = top_node;
dfs_stack_array[stack_size - 1].guvern_program__data_member__neighbour_j = neighbours_begin_array[top_node];
current_dfs_number += 1;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (0 < stack_size)) {
top_node = dfs_stack_array[stack_size - 1].guvern_program__data_member__node_x;
n_index = dfs_stack_array[stack_size - 1].guvern_program__data_member__neighbour_j;
if (neighbours_begin_array[top_node + 1] == n_index) {
if (2 <= stack_size) {
/* Move to node one level below the call stack, to its next neighbour. */
dfs_stack_array[stack_size - 2].guvern_program__data_member__neighbour_j += 1;
}
else {
/* Next step will end visiting all the neighbours of root. */
}
dfs_stack_array[stack_size - 1].guvern_program__data_member__node_x = number_of_nodes;
dfs_stack_array[stack_size - 1].guvern_program__data_member__neighbour_j = neighbours_sentinel;
stack_size -= 1;
}
else {
parent_node = dfs_parent_array[top_node];
neighbour = neighbours_lists_array[n_index];
if (parent_node == neighbour) {
/* The current neighbour is the parent, and let’s simply move on to the next neighbour. */
dfs_stack_array[stack_size - 1].guvern_program__data_member__neighbour_j = (1 + n_index);
}
else {
if (number_of_nodes != dfs_parent_array[neighbour]) {
/* Have just detected a cycle, the tree like data is not a tree. */
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
dfs_parent_array[neighbour] = top_node;
current_dfs_number += 1;
dfs_stack_array[stack_size].guvern_program__data_member__node_x = neighbour;
dfs_stack_array[stack_size].guvern_program__data_member__neighbour_j = neighbours_begin_array[neighbour];
stack_size += 1;
}
}
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (current_dfs_number != number_of_nodes) {
/* Not a tree, the graph is disconnected. */
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
}
}
}
/* Step is it returns the exit status, to the caller. */ {
return exit_status;
}
}
static int guvern_program__code__read_input__part_3 (struct guvern_program__struct__program_data * program_data) {
/** It reads, validates, and initializes the nodes values data.
***
*** • It continues the adventure of reading the input, picking up where it left off, which is reading the array of values, one for each node.
***
*** • It sorts these values, it verifies after sorting that indeed the values from the file were unique, no repeated value.
***
*** • It associates each node with the position of its value in the ascending sorting order, an integer much practical to use with the counting set.
***
*** ‣ The counting set is something useful to solving the dynamic programming part of the problem, further along in the enclosing computation.
**/
/* Step is define and O(1) initialize a handflul of variables local to the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
int exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
FILE ( * const input_file) = program_data->guvern_program__data_member__input_file;
size_t const number_of_nodes = program_data->guvern_program__data_member__number_of_nodes;
struct guvern_program__struct__node_and_its_value ( * const node_values_merge_array) = program_data->guvern_program__data_member__node_values_merge_array;
struct guvern_program__struct__node_and_its_value ( * const node_values_sort_array) = program_data->guvern_program__data_member__node_values_sort_array;
struct guvern_program__struct__merge_sort_stack_frame ( * merge_sort_stack_array) = program_data->guvern_program__data_member__merge_sort_stack_array;
size_t ( * const node_rank_array) = program_data->guvern_program__data_member__node_rank_array;
size_t ( * const rank_node_array) = program_data->guvern_program__data_member__rank_node_array;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is read the node values from the input file. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (SIZE_MAX < 1000000001) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int s_code = 0;
size_t node_x = 0;
int32_t value_v = 0;
node_x = 0;
node_values_sort_array[node_x].guvern_program__data_member__the_node_itself = node_x;
node_values_sort_array[node_x].guvern_program__data_member__the_value_itself = 1000000001;
node_x = 1;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (number_of_nodes > node_x)) {
s_code = fscanf(input_file, "%" SCNi32, &value_v);
if (1 != s_code) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
if ((value_v < -1000000000) || (+1000000000 < value_v)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
}
else {
node_values_sort_array[node_x].guvern_program__data_member__the_node_itself = node_x;
node_values_sort_array[node_x].guvern_program__data_member__the_value_itself = value_v;
node_x += 1;
}
}
}
}
}
/* Step is merge sort the node values. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (2 > number_of_nodes) {
/** Nothing to do, the array is vacuously sorted. **/
}
else { /* 2 ≤ number_of_nodes, and let’s sort this array, in ascending order of its node values, already! */
size_t const commence_sorting_initial_half = 0;
size_t const merge_initial_half = 1;
size_t const merge_final_half = 2;
size_t const merge_both_halves = 3;
size_t const commence_sorting_final_half = 4;
size_t merge_sort_stack_size = 0;
size_t problem_begin = 0;
size_t problem_end = 0;
size_t subproblem = 0;
size_t merge_begin = 0;
size_t merge_end = 0;
merge_sort_stack_size = 1;
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_begin = 0;
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_end = number_of_nodes;
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = commence_sorting_initial_half;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (0 < merge_sort_stack_size)) {
problem_begin = merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_begin;
problem_end = merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_end;
subproblem = merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem;
if (commence_sorting_initial_half == subproblem) {
/* Step is commence sorting first half. */ {
size_t const subproblem_begin = problem_begin;
size_t const subproblem_end = problem_begin + (problem_end - problem_begin) / 2;
if (3 <= (subproblem_end - subproblem_begin)) {
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_begin = subproblem_begin;
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_end = subproblem_end;
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_subproblem = commence_sorting_initial_half;
merge_sort_stack_size += 1;
}
else {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = merge_initial_half;
}
}
}
else {
if (commence_sorting_final_half == subproblem) {
/* Step is to commence sorting the final half. */ {
size_t const subproblem_begin = problem_begin + (problem_end - problem_begin) / 2;
size_t const subproblem_end = problem_end;
if (3 <= (subproblem_end - subproblem_begin)) {
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_begin = subproblem_begin;
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_end = subproblem_end;
merge_sort_stack_array[merge_sort_stack_size].guvern_program__data_member__index_subproblem = commence_sorting_initial_half;
merge_sort_stack_size += 1;
}
else {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = merge_final_half;
}
}
}
else { /* merge (2) first half, (3) second half, (4) both halves, and … goto next step, without explicitly using a goto statement */
/* Step is determine the range to merge, a whole convoluted story, just not to have the call-stack. */ {
if (merge_initial_half == subproblem) {
merge_begin = problem_begin;
merge_end = problem_begin + (problem_end - problem_begin) / 2;
}
else {
if (merge_final_half == subproblem) {
merge_begin = problem_begin + (problem_end - problem_begin) / 2;
merge_end = problem_end;
}
else {
if (merge_both_halves == merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem) {
merge_begin = merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_begin;
merge_end = merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_end;
}
else {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
}
}
}
/* Step is merge in ascending order, the two halves each already in ascending order, in one fell swoop. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (2 <= (merge_end - merge_begin)) {
/* merge, here */
size_t output_tape_index = 0;
size_t first_half_index = merge_begin;
size_t second_half_index = merge_begin + (merge_end - merge_begin) / 2;
size_t const first_half_end = second_half_index;
int32_t value_first = 0;
int32_t value_second = 0;
size_t whole_index = 0;
while ((first_half_index < first_half_end) && (second_half_index < merge_end)) {
value_first = node_values_sort_array[first_half_index ].guvern_program__data_member__the_value_itself;
value_second = node_values_sort_array[second_half_index].guvern_program__data_member__the_value_itself;
if (value_first < value_second) {
node_values_merge_array[output_tape_index] = node_values_sort_array[first_half_index];
first_half_index += 1;
}
else {
node_values_merge_array[output_tape_index] = node_values_sort_array[second_half_index];
second_half_index += 1;
}
output_tape_index += 1;
}
while (first_half_index < first_half_end) {
node_values_merge_array[output_tape_index] = node_values_sort_array[first_half_index];
first_half_index += 1;
output_tape_index += 1;
}
while (second_half_index < merge_end) {
node_values_merge_array[output_tape_index] = node_values_sort_array[second_half_index];
second_half_index += 1;
output_tape_index += 1;
}
output_tape_index = 0;
whole_index = merge_begin;
while (whole_index < merge_end) {
node_values_sort_array[whole_index] = node_values_merge_array[output_tape_index];
output_tape_index += 1;
whole_index += 1;
}
}
}
}
/* Step is determine where to continue, next step, goto considered harmful, ha ha. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (merge_initial_half == subproblem) {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = commence_sorting_final_half;
}
else {
if (merge_final_half == merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem) {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = merge_both_halves;
}
else {
if (merge_both_halves == merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem) {
merge_sort_stack_size -= 1;
if (1 <= merge_sort_stack_size) {
if (commence_sorting_initial_half == merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem) {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = commence_sorting_final_half;
}
else {
if (commence_sorting_final_half == merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem) {
merge_sort_stack_array[merge_sort_stack_size - 1].guvern_program__data_member__index_subproblem = merge_both_halves;
}
else {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
}
}
else {
/* Have just sorted the array. */
}
}
else {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
}
}
}
}
}
}
}
}
}
}
/* Step is validate that the node values are indeed unique. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t node_rank = 1;
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (number_of_nodes > node_rank)) {
if (node_values_sort_array[node_rank - 1].guvern_program__data_member__the_value_itself >= node_values_sort_array[node_rank].guvern_program__data_member__the_value_itself) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
/** exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
***
*** Also possible, either incorrect implementation or invalid input, one of the two …
***
*** Let’s see the glass half full, and suppose invalid input, why not?!
**/
}
else {
node_rank += 1;
}
}
}
}
/* Step is rank the nodes. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t rank_r = 0;
size_t node_n = 0;
while (number_of_nodes > rank_r) {
node_n = node_values_sort_array[rank_r].guvern_program__data_member__the_node_itself;
node_rank_array[node_n] = rank_r;
rank_r += 1;
}
}
}
/* Step is determine for each rank, its unique corresponding node. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t node_n = 0;
size_t rank_r = 0;
while (number_of_nodes > node_n) {
rank_r = node_rank_array[node_n];
rank_node_array[rank_r] = node_n;
node_n += 1;
}
}
}
/* Step is return the exit status, nothing more, nothing less. */ {
return exit_status;
}
}
static int guvern_program__code__solve_the_problem (struct guvern_program__struct__program_data * program_data) {
/** It solves the problem, computing its unique answer, by dynamic programming on the tree.
***
***
*** • It solves the problem by dynamic programming on maximum_contribution_array[x].
***
*** ‣ DP on a tree!
***
*** ‣ Everything is at hand:
***
*** ※ the adjacency lists … array,
***
*** ※ the dfs begin and dfs end numbers, one of these for each node,
***
*** ※ the most recent contributor array,
***
*** ※ the maximum contribution array,
***
*** • Let the actual problem solving finally begin!
***
*** ‣ Let's go!
***
**/
/* Step is define and O(1) initialize a handful of variable local into the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
int exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
size_t const number_of_nodes = program_data->guvern_program__data_member__number_of_nodes;
size_t const ( * const node_rank_array ) = program_data->guvern_program__data_member__node_rank_array;
size_t const ( * const rank_node_array ) = program_data->guvern_program__data_member__rank_node_array;
size_t const ( * const neighbours_lists_array ) = program_data->guvern_program__data_member__neighbours_lists_array;
size_t const ( * const neighbours_begin_array ) = program_data->guvern_program__data_member__neighbours_begin_array;
struct guvern_program__struct__counting_set * counting_set = program_data->guvern_program__data_member__counting_set;
struct guvern_program__struct__dfs_stack_frame ( * const dfs_stack_array ) = program_data->guvern_program__data_member__dfs_stack_array;
size_t ( * const sink_cache_array ) = program_data->guvern_program__data_member__sink_cache_array;
size_t ( * const snapshot_contribution_array ) = program_data->guvern_program__data_member__snapshot_contribution_array;
size_t ( * const maximum_contribution_array ) = program_data->guvern_program__data_member__maximum_contribution_array;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is initialize the sink cache array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t node_x = 0;
node_x = 0;
while (number_of_nodes > node_x) {
sink_cache_array[node_x] = number_of_nodes;
node_x += 1;
}
}
}
/* Step is initialize the snapshot contribution array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t node_x = 0;
node_x = 0;
while (number_of_nodes > node_x) {
snapshot_contribution_array[node_x] = 0;
node_x += 1;
}
}
}
/* Step is initialize the maximum contribution array. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
size_t node_x = 0;
node_x = 0;
while (number_of_nodes > node_x) {
maximum_contribution_array[node_x] = 0;
node_x += 1;
}
}
}
/* Step is do the the depth first search implemented by means of stack with allocation storage duration. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if ((SIZE_MAX - (number_of_nodes - 1)) < (number_of_nodes - 1)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__IMPLEMENTATION_LIMIT__SIZE_T;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
/* Step is define and O(1) initialize a handful of variables local into the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
size_t const neighbours_sentinel = (number_of_nodes - 1) + (number_of_nodes - 1);
size_t const tree_root = 0; /* node 1, backed down one unit, to be zero based. */
size_t dfs_stack_size = 0;
size_t top_node = 0;
size_t rank_top = 0;
size_t parent_node = 0;
size_t n_index = 0;
size_t neighbour = 0;
size_t rank_neighbour = 0;
size_t rank_sink = 0;
size_t sink_node = 0;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is initialize the depth first stack. */ {
guvern_program__code__counting_set__initialize_as_empty_set(counting_set);
dfs_stack_size = 0;
top_node = tree_root;
n_index = neighbours_begin_array[top_node];
dfs_stack_array[dfs_stack_size].guvern_program__data_member__node_x = top_node;
dfs_stack_array[dfs_stack_size].guvern_program__data_member__neighbour_j = n_index;
maximum_contribution_array[top_node] = 1;
rank_top = node_rank_array[top_node];
guvern_program__code__counting_set__insert_value(counting_set, rank_top);
dfs_stack_size += 1;
}
/* Step is loop the depth first search, already. */ {
while ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (0 < dfs_stack_size)) {
top_node = dfs_stack_array[dfs_stack_size - 1].guvern_program__data_member__node_x;
n_index = dfs_stack_array[dfs_stack_size - 1].guvern_program__data_member__neighbour_j;
if (neighbours_begin_array[1 + top_node] == n_index) {
/* Step is update the contribution of the top node itself, having now fully processed all its descendants except itself. */ {
if (top_node != tree_root) {
sink_node = sink_cache_array[top_node];
if (maximum_contribution_array[sink_node] - snapshot_contribution_array[top_node] < maximum_contribution_array[top_node]) {
maximum_contribution_array[sink_node] -= (maximum_contribution_array[sink_node] - snapshot_contribution_array[top_node]);
maximum_contribution_array[sink_node] += maximum_contribution_array[top_node];
}
else {
/* Better is that top_node does not contribute itself, to the maximum contribution of its sink node. */
}
}
}
/* Step is drop stack frame, and advance to the next neighbour in parent stack frame. */ {
if (2 <= dfs_stack_size) {
dfs_stack_array[dfs_stack_size - 2].guvern_program__data_member__neighbour_j += 1;
}
rank_top = node_rank_array[top_node];
guvern_program__code__counting_set__remove_value(counting_set, rank_top);
dfs_stack_array[dfs_stack_size - 1].guvern_program__data_member__node_x = number_of_nodes; /* forget about it … */
dfs_stack_array[dfs_stack_size - 1].guvern_program__data_member__neighbour_j = neighbours_sentinel;
dfs_stack_size -= 1;
}
}
else {
/* Step is visit the neighbour if by exclusion it is a child, not the parent. */ {
parent_node = (2 <= dfs_stack_size) ? dfs_stack_array[dfs_stack_size - 2].guvern_program__data_member__node_x : number_of_nodes;
neighbour = neighbours_lists_array[n_index];
if (parent_node == neighbour) {
dfs_stack_array[dfs_stack_size - 1].guvern_program__data_member__neighbour_j += 1;
}
else {
dfs_stack_array[dfs_stack_size].guvern_program__data_member__node_x = neighbour;
dfs_stack_array[dfs_stack_size].guvern_program__data_member__neighbour_j = neighbours_begin_array[neighbour];
maximum_contribution_array[neighbour] = 1;
rank_neighbour = node_rank_array[neighbour];
guvern_program__code__counting_set__insert_value(counting_set, rank_neighbour);
rank_sink = guvern_program__code__counting_set__query_least_larger_value(counting_set, rank_neighbour);
if (number_of_nodes == rank_sink) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__INCORECT_IMPLEMENTATION__LOGIC_ERROR;
}
else {
sink_node = rank_node_array[rank_sink];
snapshot_contribution_array[neighbour] = maximum_contribution_array[sink_node];
sink_cache_array[neighbour] = sink_node;
dfs_stack_size += 1;
}
}
}
}
}
}
}
}
/* Step is collect the answer computed by the depth first search, earlier on. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
program_data->guvern_program__data_member__the_answer = maximum_contribution_array[0] - 1;
}
}
/* Step is return the exit status, nothing more and nothing less. */ {
return exit_status;
}
}
static int guvern_program__code__write_the_answer (struct guvern_program__struct__program_data * program_data) {
/** Writes the already found answer.
***
*** • The problem is like a question for which the program determines the answer.
***
*** • This one, this routine, writes in the output file, this computed answer.
***
***/
int exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
FILE ( * const output_file ) = program_data->guvern_program__data_member__output_file;
size_t const the_answer = program_data->guvern_program__data_member__the_answer;
int const p_code = fprintf(output_file, "%zu\n", the_answer);
if (0 >= p_code) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUTPUT_FILE;
}
return exit_status;
}
static int guvern_program__code__release_program_data (struct guvern_program__struct__program_data * program_data) {
/** Relinquish the memory, not that it matters in this particular case, but on principle.
***
***
*** • It deallocates program data, in reverse allocation order.
***
**/
int exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
if (NULL != program_data) {
int c_code = 0;
program_data->guvern_program__data_member__the_answer = 0; /* forget about it */
free(program_data->guvern_program__data_member__maximum_contribution_array);
program_data->guvern_program__data_member__maximum_contribution_array = NULL;
free(program_data->guvern_program__data_member__snapshot_contribution_array);
program_data->guvern_program__data_member__snapshot_contribution_array = NULL;
free(program_data->guvern_program__data_member__sink_cache_array);
program_data->guvern_program__data_member__sink_cache_array = NULL;
free(program_data->guvern_program__data_member__rank_node_array);
program_data->guvern_program__data_member__rank_node_array = NULL;
free(program_data->guvern_program__data_member__node_rank_array);
program_data->guvern_program__data_member__node_rank_array = NULL;
free(program_data->guvern_program__data_member__merge_sort_stack_array);
program_data->guvern_program__data_member__merge_sort_stack_array = NULL;
free(program_data->guvern_program__data_member__node_values_sort_array);
program_data->guvern_program__data_member__node_values_sort_array = NULL;
free(program_data->guvern_program__data_member__node_values_merge_array);
program_data->guvern_program__data_member__node_values_merge_array = NULL;
free(program_data->guvern_program__data_member__dfs_parent_array);
program_data->guvern_program__data_member__dfs_parent_array = NULL;
free(program_data->guvern_program__data_member__edges_array);
program_data->guvern_program__data_member__edges_array = NULL;
guvern_program__code__counting_set__release(program_data->guvern_program__data_member__counting_set);
program_data->guvern_program__data_member__counting_set = NULL;
free(program_data->guvern_program__data_member__dfs_stack_array);
program_data->guvern_program__data_member__dfs_stack_array = NULL;
free(program_data->guvern_program__data_member__neighbours_begin_array);
program_data->guvern_program__data_member__neighbours_begin_array = NULL;
free(program_data->guvern_program__data_member__neighbours_lists_array);
program_data->guvern_program__data_member__neighbours_lists_array = NULL;
program_data->guvern_program__data_member__number_of_nodes = 0;
c_code = fclose(program_data->guvern_program__data_member__output_file);
program_data->guvern_program__data_member__output_file = NULL;
if ((GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) && (0 != c_code)) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__OUTPUT_FILE;
perror("Could not close the output file.");
}
c_code = fclose(program_data->guvern_program__data_member__input_file);
program_data->guvern_program__data_member__input_file = NULL;
if (0 != c_code) {
exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__NAY_FAILURE__RUNTIME_ERROR__INPUT_FILE;
perror("Could not close the input file.");
}
free(program_data);
program_data = NULL;
}
return exit_status;
}
int main (void) {
/** This one is the main function. */
/* Step is define and O(1) initialize a handful of variables local to the immediately enclosing block scope. */ {
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__OPEN
int exit_status = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
struct guvern_program__struct__program_data * program_data = NULL;
GUVERN_PROGRAM__MACRO__FOLDING__INVERTED_BLOCK_SCOPE_BRACKETS__CLOSE
}
/* Step is read the data. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int exit_status_too = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
exit_status_too = guvern_program__code__read_input__part_1(&program_data);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int exit_status_too = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
exit_status_too = guvern_program__code__read_input__part_2(program_data);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int exit_status_too = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
exit_status_too = guvern_program__code__read_input__part_3(program_data);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is solve the problem. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
int exit_status_too = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
exit_status_too = guvern_program__code__solve_the_problem(program_data);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status_too) {
exit_status = exit_status_too;
}
}
}
/* Step is write the answer. */ {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
exit_status = guvern_program__code__write_the_answer(program_data);
}
}
/* Step is relinquish the program data. */ {
int exit_status__too = GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE;
exit_status__too = guvern_program__code__release_program_data(program_data);
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE == exit_status) {
if (GUVERN_PROGRAM__MACRO__EXIT_STATUS__AYE_SUCCESS__ALL_WAS_FINE != exit_status__too) {
exit_status = exit_status__too;
}
}
}
/* Step is return the status code, nohting more and nothing less. */ {
return exit_status;
}
}
#endif
Marius B mgnt