Cod sursa(job #2909476)
| Utilizator |  Marius B mgnt |
Data | 13 iunie 2022 21:29:56 |
|---|---|---|---|
| Problema | Mesaj4 | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 51.76 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <memory>
#include <limits>
#include <stdexcept>
#include <algorithm>
#include <numeric>
struct edge_type {
uint32_t idm__u2;
uint32_t idm__u5;
};
edge_type build_edge (uint32_t arg__u2, uint32_t arg__u5) {
edge_type as__edge;
as__edge.idm__u2 = arg__u2;
as__edge.idm__u5 = arg__u5;
return as__edge;
}
struct mesaj4_type {
size_t idm__n = 0;
size_t idm__m = 0;
std::vector<edge_type> idm__edges;
std::vector<uint32_t> idm__neighbours_first;
std::vector<uint32_t> idm__neighbours_array;
std::vector<uint32_t> idm__queue;
std::vector<uint32_t> idm__parent;
size_t idm__cc;
};
template <typename T>
inline
T read_scalar_value_from_input_stream (std::istream & arg__is) {
T as__value;
arg__is >> as__value;
return as__value;
}
size_t double_that (size_t arg__m) {
size_t const as__maxval = std::numeric_limits<size_t>::max();
if ((as__maxval - arg__m) < arg__m) {
throw std::runtime_error("Implementation limits us."); }
return (arg__m + arg__m);
}
size_t one_plus (size_t arg__n) {
size_t const as__maxval = std::numeric_limits<size_t>::max();
if ((as__maxval - arg__n) < 1) {
throw std::runtime_error("Implementation limits us."); }
return (arg__n + 1);
}
void problem_mesaj4__read_the_input__all_of_it (mesaj4_type & arg__problem) {
std::ifstream as__is;
as__is.exceptions(std::ifstream::failbit | std::ifstream::badbit);
as__is.open("mesaj4.in");
uint64_t const as__n = read_scalar_value_from_input_stream<uint64_t>(as__is);
uint64_t const as__m = read_scalar_value_from_input_stream<uint64_t>(as__is);
if ((1 > as__n) || (100'000 < as__n)) {
throw std::invalid_argument("n."); }
if ((1 > as__m) || (100'000 < as__m)) {
throw std::invalid_argument("k."); }
std::vector<edge_type> as__edges(as__m);
size_t as__m2 = 0;
uint32_t as__u2 = 0;
uint32_t as__u5 = 0;
size_t as__j = 0;
for (as__j = 0; as__m > as__j; ++as__j) {
as__u2 = read_scalar_value_from_input_stream<uint32_t>(as__is);
as__u5 = read_scalar_value_from_input_stream<uint32_t>(as__is);
if ((1 > as__u2) || (1 > as__u5) || (as__n < as__u2) || (as__n < as__u5)) {
throw std::invalid_argument("one edge has been found to be out of whack."); }
if (as__u2 != as__u5) {
// Self loops would make no progress, in the message passing game.
// It does not matter if one is friend with oneself, in this game.
as__edges.at(as__m2) = build_edge(as__u2 - 1, as__u5 - 1);
as__m2 += 1; }}
if (as__m2 < as__m) {
as__edges.resize(as__m2); }
// Pass the baton!
arg__problem.idm__n = as__n;
arg__problem.idm__m = as__m2;
as__edges.swap(arg__problem.idm__edges);
}
void problem_mesaj4__allocate_all_the_space__id_est_memory__all_of_it (mesaj4_type & arg__problem) {
/* Having read the edges, let’s allocate all the memory this program will use, mostly, in advance. */
size_t const as__n0 = arg__problem.idm__n;
size_t const as__n2 = one_plus(as__n0);
size_t const as__m2 = arg__problem.idm__m;
size_t const as__m4 = double_that(as__m2);
std::vector<uint32_t> as__first(as__n2);
std::vector<uint32_t> as__array(as__m4);
std::vector<uint32_t> as__queue(as__n0);
std::vector<uint32_t> as__parent(as__n0);
// Pass the baton!
as__first.swap(arg__problem.idm__neighbours_first);
as__array.swap(arg__problem.idm__neighbours_array);
as__queue.swap(arg__problem.idm__queue);
as__parent.swap(arg__problem.idm__parent);
}
void problem_mesaj4__preprocess_neighbours_arrays__in_preparation_for_our_traversal_of_the_friendship_graph (mesaj4_type & arg__problem) {
/* Now that the memory is all acquired, precompute the two arrays to be used for traversing the friendship graph. */
size_t const as__n0 = arg__problem.idm__n;
size_t const as__m2 = arg__problem.idm__m;
std::vector<edge_type> const & as__edges = arg__problem.idm__edges;
std::vector<uint32_t> & as__first = arg__problem.idm__neighbours_first;
std::vector<uint32_t> & as__array = arg__problem.idm__neighbours_array;
// For each node u, compute its degree.
std::fill(as__first.begin(), as__first.begin() + as__n0, static_cast<uint32_t>(0));
size_t as__j = 0;
size_t as__u7 = 0;
size_t as__u8 = 0;
edge_type const * as__ep = nullptr;
for (as__j = 0; as__m2 > as__j; ++as__j) {
as__ep = &(as__edges.at(as__j));
as__u7 = static_cast<size_t>(as__ep->idm__u2);
as__u8 = static_cast<size_t>(as__ep->idm__u5);
as__first.at(as__u7) += 1;
as__first.at(as__u8) += 1; }
// Based on the degree values just computed, compute for its edge, from where we may lay out its neighbours,
// i.e. the position for its first neighbour in the shared array of neighbours, shared among all the nodes.
size_t as__count = 0;
size_t as__last = 0;
for (as__j = 0; as__n0 > as__j; ++as__j) {
as__count = static_cast<size_t>(as__first.at(as__j));
as__first.at(as__j) = static_cast<uint32_t>(as__last);
as__last += as__count; }
// Tread the array of starting positions just computed, as an array of current positions, and lay out neighbours,
// for all nodes, at once, intertwined; bookkeeping delight, also as__j used at its full potential, this code.
for (as__j = 0; as__m2 > as__j; ++as__j) {
as__ep = &(as__edges.at(as__j));
as__u7 = static_cast<size_t>(as__ep->idm__u2);
as__u8 = static_cast<size_t>(as__ep->idm__u5);
as__array.at(as__first.at(as__u7)) = static_cast<uint32_t>(as__u8);
as__first.at(as__u7) += 1;
as__array.at(as__first.at(as__u8)) = static_cast<uint32_t>(as__u7);
as__first.at(as__u8) += 1; }
// For each node u, compute its degree; repetition makes perfect!
std::fill(as__first.begin(), as__first.begin() + as__n0, static_cast<uint32_t>(0));
for (as__j = 0; as__m2 > as__j; ++as__j) {
as__ep = &(as__edges.at(as__j));
as__u7 = static_cast<size_t>(as__ep->idm__u2);
as__u8 = static_cast<size_t>(as__ep->idm__u5);
as__first.at(as__u7) += 1;
as__first.at(as__u8) += 1; }
// Based on the degree values just computed, compute for its edge, from where we may lay out its neighbours,
// i.e. the position for its first neighbour in the shared array of neighbours, shared among all the nodes.
as__last = 0;
for (as__j = 0; as__n0 > as__j; ++as__j) {
as__count = static_cast<size_t>(as__first.at(as__j));
as__first.at(as__j) = static_cast<uint32_t>(as__last);
as__last += as__count; }
// Also, store the position where the neighbours of our sentinel would start.
// We want this sentinel, to be able to easily iterate neighbours, for each node, including the last.
as__first.at(as__n0) = as__last;
}
void problem_mesaj4__determine_a_solution_if_there_exists_any_at_all (mesaj4_type & arg__problem) {
// In any one sequence of moves that manages to pass all the messages to every node, there is precisely one node y which receives all
// messages first; before y receives all its messages, from each node x, x ≠ y, there must be a step where x transmits all its messages
// to some other node x' so that x − x' is an edge in the friendship graph; similarly, after y receives all its messages,
// for each node z, z ≠ y, there must be a step when z receives its messages from some node z', such that
// z' − z is an edge in the friendship graph.
// In the light of this necessity, we see that if there exists at least one spanning tree for the whole graph,
// i.e. the graph is connected, then the problem has a solution: simply move inwardly in the spanning tree to some
// arbitrary node x, then in a second, and final, stage, simply move outwardly from the same node x, in the spanning tree,
// and at each move, pass all messages.
// To solve, we build a breadth first search traversal sequence, into a queue, while also storing for each node, its parent.
size_t const as__n0 = arg__problem.idm__n;
std::vector<uint32_t> & as__queue = arg__problem.idm__queue;
std::vector<uint32_t> & as__parent = arg__problem.idm__parent;
std::vector<uint32_t> const & as__neighbours_first = arg__problem.idm__neighbours_first;
std::vector<uint32_t> const & as__neighbours_array = arg__problem.idm__neighbours_array;
std::iota(as__parent.begin(), as__parent.end(), static_cast<uint32_t>(0));
size_t as__queue_position_insert = 0;
size_t as__queue_position_extract = 0;
as__queue.at(as__queue_position_insert) = static_cast<uint32_t>(0);
as__queue_position_insert += 1;
as__parent.at(0) = static_cast<uint32_t>(as__n0);
size_t as__u2 = 0;
size_t as__u5 = 0;
size_t as__j = 0;
size_t as__h = 0;
size_t as__cc = as__n0;
while (as__queue_position_extract < as__queue_position_insert) {
as__u2 = static_cast<size_t>(as__queue.at(as__queue_position_extract));
as__queue_position_extract += 1;
as__j = static_cast<size_t>(as__neighbours_first.at(as__u2 + 0));
as__h = static_cast<size_t>(as__neighbours_first.at(as__u2 + 1));
for (/* Non sequitur: */static_cast<void>(std::boolalpha); as__h > as__j; ++as__j) {
as__u5 = static_cast<size_t>(as__neighbours_array.at(as__j));
if (as__parent.at(as__u5) == as__u5) {
as__queue.at(as__queue_position_insert) = static_cast<uint32_t>(as__u5);
as__queue_position_insert += 1;
as__parent.at(as__u5) = static_cast<uint32_t>(as__u2);
as__cc -= 1; }}}
arg__problem.idm__cc = as__cc;
}
void problem_mesaj4__write_the_solution_or_lack_of_any_such_thing_and_be_done_with_it (mesaj4_type & arg__problem) {
std::ofstream as__os;
as__os.exceptions(std::ifstream::failbit | std::ifstream::badbit);
as__os.open("mesaj4.out");
size_t const as__cc = arg__problem.idm__cc;
if (as__cc > 1) {
as__os << -1 << '\n';
return; }
size_t const as__n0 = arg__problem.idm__n;
std::vector<uint32_t> const & as__queue = arg__problem.idm__queue;
std::vector<uint32_t> const & as__parent = arg__problem.idm__parent;
size_t as__j = 0;
size_t as__u2 = 0;
size_t as__u5 = 0;
as__os << ((as__n0 - 1) * 2) << '\n';
for (as__j = as__n0 - 1; 0 < as__j; --as__j) {
as__u5 = static_cast<size_t>(as__queue.at(as__j));
as__u2 = static_cast<size_t>(as__parent.at(as__u5));
as__os << (1 + as__u5) << ' ' << (1 + as__u2) << '\n'; }
for (as__j = 1; as__n0 > as__j; ++as__j) {
as__u5 = static_cast<size_t>(as__queue.at(as__j));
as__u2 = static_cast<size_t>(as__parent.at(as__u5));
as__os << (1 + as__u2) << ' ' << (1 + as__u5) << '\n'; }
}
void demo (void) {
mesaj4_type as__problem;
problem_mesaj4__read_the_input__all_of_it(as__problem);
problem_mesaj4__allocate_all_the_space__id_est_memory__all_of_it (as__problem);
problem_mesaj4__preprocess_neighbours_arrays__in_preparation_for_our_traversal_of_the_friendship_graph (as__problem);
problem_mesaj4__determine_a_solution_if_there_exists_any_at_all (as__problem);
problem_mesaj4__write_the_solution_or_lack_of_any_such_thing_and_be_done_with_it (as__problem);
}
void lament (std::exception const & as__exc) {
try {
std::cerr << as__exc.what() << std::endl; }
catch ( ... ) {
/* Oh, dear! */ }
}
int main (void) {
int status = 23;
try {
demo();
status = 0; }
catch (std::exception const & as__exc) {
lament(as__exc);
status = 19; }
catch ( ... ) {
status = 17; }
return status;
}
