Cod sursa(job #2794093)
| Utilizator |  Marius B mgnt |
Data | 4 noiembrie 2021 12:15:45 |
|---|---|---|---|
| Problema | Andrei | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 67.4 kb |
#define FOLD__SCOPE
#include <fstream>
#include <cstddef>
#include <vector>
#include <algorithm>
#include <numeric>
struct Edge {
// idm__, prefix for instance data members
uint32_t idm__a;
uint32_t idm__b;
inline void assign_from (uint32_t arg__a, uint32_t arg__b) noexcept {
idm__a = arg__a;
idm__b = arg__b; }
inline void assign_to (uint32_t & arg__a, uint32_t & arg__b) const noexcept {
arg__a = idm__a;
arg__b = idm__b; }
};
struct Problem {
size_t idm__n = 0;
size_t idm__m = 0;
size_t idm__edge_start_white = 0;
size_t idm__edge_end___white = 0;
size_t idm__edge_start_red = 0;
size_t idm__edge_end___red = 0;
size_t idm__edge_start_purple = 0;
size_t idm__edge_end___purple = 0;
std::vector<Edge> idm__edges_array;
std::vector<uint32_t> idm__adj_index;
std::vector<uint32_t> idm__adj_array;
std::vector<uint8_t> idm__visited;
std::vector<uint32_t> idm__kosaraju_list;
std::vector<uint32_t> idm__scc_indicator;
std::vector<uint8_t> idm__partition;
};
struct ContextForDfsOnOutgoingEdges {
std::vector<uint8_t> * idm__visited = nullptr;
std::vector<uint32_t> * idm__adj_index = nullptr;
std::vector<uint32_t> * idm__adj_array = nullptr;
std::vector<uint32_t> * idm__out_array = nullptr;
size_t idm__out_pos = 0;
};
void dfs_on_outedges (ContextForDfsOnOutgoingEdges & arg__ctx, uint32_t arg__x) {
arg__ctx.idm__visited->at(arg__x) = 1;
for (uint32_t as__i = arg__ctx.idm__adj_index->at(arg__x + 0); arg__ctx.idm__adj_index->at(arg__x + 1) > as__i; ++as__i) {
if (0 == arg__ctx.idm__visited->at(arg__ctx.idm__adj_array->at(as__i))) {
dfs_on_outedges (arg__ctx, arg__ctx.idm__adj_array->at(as__i)); }}
arg__ctx.idm__out_array->at(arg__ctx.idm__out_pos - 1) = arg__x;
arg__ctx.idm__out_pos -= 1;
}
struct ContextForDfsOnIncomingEdges {
std::vector<uint32_t> * idm__adj_index = nullptr;
std::vector<uint32_t> * idm__adj_array = nullptr;
std::vector<uint8_t> * idm__visited = nullptr;
std::vector<uint32_t> * idm__scc_indicator = nullptr;
uint32_t idm__scc_current = 0;
};
void dfs_on_incoming_edges (ContextForDfsOnIncomingEdges & arg__ctx, uint32_t arg__x) {
arg__ctx.idm__visited->at(arg__x) = 1;
arg__ctx.idm__scc_indicator->at(arg__x) = arg__ctx.idm__scc_current;
for (uint32_t as__i = arg__ctx.idm__adj_index->at(arg__x + 0); arg__ctx.idm__adj_index->at(arg__x + 1) > as__i; ++as__i) {
if (0 == arg__ctx.idm__visited->at(arg__ctx.idm__adj_array->at(as__i))) {
dfs_on_incoming_edges (arg__ctx, arg__ctx.idm__adj_array->at(as__i)); }}
}
void read_the_graph (Problem & arg__problem) {
/// It reads the graph from the input file, and allocates the memory for later use.
size_t as__n = 0; size_t as__m = 0;
std::ifstream as__is("andrei.in");
as__is >> as__n >> as__m;
if ((1 > as__n) || (100000 < as__n) || (1 > as__m) || (200000 < as__m)) {
throw std::runtime_error("Invalid graph size."); }
std::vector<Edge> as__edges_array(as__m);
std::vector<uint32_t> as__adj_index(as__n + as__n + 1);
std::vector<uint32_t> as__adj_array(as__m * 4);
std::vector<uint8_t> as__visited(as__n + as__n);
std::vector<uint32_t> as__kosaraju_list(as__n + as__n);
std::vector<uint32_t> as__scc_indicator(as__n + as__n);
std::vector<uint8_t> as__partition; // 0 sized, intentionally.
size_t as__i = 0; uint32_t as__a = 0; uint32_t as__b = 0; uint32_t as__c = 0;
size_t as__f = 0; size_t as__g = 0; size_t as__h = 0;
for (as__i = 0; as__m > as__i; ++as__i) {
as__is >> as__a >> as__b >> as__c;
if ((1 > as__a) || (as__n < as__a) || (1 > as__b) || (as__n < as__b) || (2 < as__c)) {
throw std::runtime_error("Invalid edge."); }
--as__a; --as__b;
if (2 /* Purple. */ == as__c) {
as__edges_array.at((as__m - 1) - as__h).assign_from(as__a, as__b); ++as__h; }
else {
if (1 /* Red. */ == as__c) {
as__edges_array.at(as__f + as__g).assign_from(as__a, as__b); ++as__g; }
else { /* White, 0 == as__c. */
if (0 < as__g) {
as__edges_array.at(as__f + as__g) = as__edges_array.at(as__f); }
as__edges_array.at(as__f).assign_from(as__a, as__b); ++as__f; }}}
// Okay!
arg__problem.idm__n = as__n;
arg__problem.idm__m = as__m;
arg__problem.idm__edge_start_white = 0;
arg__problem.idm__edge_end___white = as__f;
arg__problem.idm__edge_start_red = as__f;
arg__problem.idm__edge_end___red = as__f + as__g;
arg__problem.idm__edge_start_purple = as__f + as__g;
arg__problem.idm__edge_end___purple = as__f + as__g + as__h;
arg__problem.idm__edges_array.swap(as__edges_array);
arg__problem.idm__adj_index.swap(as__adj_index);
arg__problem.idm__adj_array.swap(as__adj_array);
arg__problem.idm__visited.swap(as__visited);
arg__problem.idm__kosaraju_list.swap(as__kosaraju_list);
arg__problem.idm__scc_indicator.swap(as__scc_indicator);
arg__problem.idm__partition.swap(as__partition); // It will repurpose the memory from idm__visited.
}
void partition_the_nodes (Problem & arg__problem) {
/// Solves the partitions assignment problem, by solving its associated 2SAT instance.
/* Build the implication graph associated with the 2SAT instance. */ {
size_t const as__n = arg__problem.idm__n;
size_t const as__white_start = arg__problem.idm__edge_start_white;
size_t const as__white___end = arg__problem.idm__edge_end___white;
size_t const as__red_start = arg__problem.idm__edge_start_red;
size_t const as__red___end = arg__problem.idm__edge_end___red;
size_t const as__purple_start = arg__problem.idm__edge_start_purple;
size_t const as__purple___end = arg__problem.idm__edge_end___purple;
std::vector<Edge> const & as__edges_array = arg__problem.idm__edges_array;
std::vector<uint32_t> & as__adj_index = arg__problem.idm__adj_index;
std::vector<uint32_t> & as__adj_array = arg__problem.idm__adj_array;
size_t as__i = 0; uint32_t as__a = 0; uint32_t as__b = 0;
uint32_t as__index = 0; uint32_t as__outdeg = 0;
// Scan out degrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + (as__n + as__n), 0);
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_index.at(as__n + as__a) += 1; /* ¬a → b */
as__adj_index.at(as__n + as__b) += 1; /* ¬b → a */ }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_index.at( as__a) += 1; /* a → ¬b */
as__adj_index.at( as__b) += 1; /* b → ¬a */ }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_index.at( as__a) += 1; /* a → b */
as__adj_index.at(as__n + as__b) += 1; /* ¬b → ¬a */
as__adj_index.at(as__n + as__a) += 1; /* ¬a → ¬b */
as__adj_index.at( as__b) += 1; /* b → a */ }
// Initialize adjacency lists first elements indices.
as__index = 0;
for (as__i = 0; (as__n + as__n) > as__i; ++as__i) {
as__outdeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__index;
as__index += as__outdeg; }
// Scan outgoing edges.
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_array.at(as__adj_index.at(as__n + as__a)) = as__b; /* ¬a → b */
as__adj_index.at(as__n + as__a) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__b)) = as__a; /* ¬b → a */
as__adj_index.at(as__n + as__b) += 1; }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_array.at(as__adj_index.at( as__a)) = as__n + as__b; /* a → ¬b */
as__adj_index.at( as__a) += 1;
as__adj_array.at(as__adj_index.at( as__b)) = as__n + as__a; /* b → ¬a */
as__adj_index.at( as__b) += 1; }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_array.at(as__adj_index.at( as__a)) = as__b; /* a → b */
as__adj_index.at( as__a) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__b)) = as__n + as__a; /* ¬b → ¬a */
as__adj_index.at(as__n + as__b) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__a)) = as__n + as__b; /* ¬a → ¬b */
as__adj_index.at(as__n + as__a) += 1;
as__adj_array.at(as__adj_index.at( as__b)) = as__a; /* b → a */
as__adj_index.at( as__b) += 1; }
// Scan outdegrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + (as__n + as__n), 0);
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_index.at(as__n + as__a) += 1; /* ¬a → b */
as__adj_index.at(as__n + as__b) += 1; /* ¬b → a */ }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_index.at( as__a) += 1; /* a → ¬b */
as__adj_index.at( as__b) += 1; /* b → ¬a */ }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_index.at( as__a) += 1; /* a → b */
as__adj_index.at(as__n + as__b) += 1; /* ¬b → ¬a */
as__adj_index.at(as__n + as__a) += 1; /* ¬a → ¬b */
as__adj_index.at( as__b) += 1; /* b → a */ }
// Initialize adjacency lists first elements indices.
as__index = 0;
for (as__i = 0; (as__n + as__n) > as__i; ++as__i) {
as__outdeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__index;
as__index += as__outdeg; }
// Initialize one past end node’s sentinel.
as__adj_index.at(as__n + as__n) = as__index; }
/* Rao Kosaraju’s algorithm, strongly connected components, step 1. */ {
size_t const as__n = arg__problem.idm__n;
std::vector<uint8_t> & as__visited = arg__problem.idm__visited;
std::fill(as__visited.begin(), as__visited.begin() + (as__n + as__n), 0);
ContextForDfsOnOutgoingEdges as__ctx;
as__ctx.idm__visited = &arg__problem.idm__visited;
as__ctx.idm__adj_index = &arg__problem.idm__adj_index;
as__ctx.idm__adj_array = &arg__problem.idm__adj_array;
as__ctx.idm__out_array = &arg__problem.idm__kosaraju_list;
as__ctx.idm__out_pos = (as__n + as__n);
size_t as__i = 0;
for (as__i = 0; (as__n + as__n) > as__i; ++as__i) {
if (0 == as__visited.at(as__i)) {
dfs_on_outedges (as__ctx, as__i); }}}
/* Build the transpose of the implication graph. */ {
size_t const as__n = arg__problem.idm__n;
size_t const as__white_start = arg__problem.idm__edge_start_white;
size_t const as__white___end = arg__problem.idm__edge_end___white;
size_t const as__red_start = arg__problem.idm__edge_start_red;
size_t const as__red___end = arg__problem.idm__edge_end___red;
size_t const as__purple_start = arg__problem.idm__edge_start_purple;
size_t const as__purple___end = arg__problem.idm__edge_end___purple;
std::vector<Edge> const & as__edges_array = arg__problem.idm__edges_array;
std::vector<uint32_t> & as__adj_index = arg__problem.idm__adj_index;
std::vector<uint32_t> & as__adj_array = arg__problem.idm__adj_array;
size_t as__i = 0; uint32_t as__a = 0; uint32_t as__b = 0;
uint32_t as__index = 0; uint32_t as__indeg = 0;
// Scan indegrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + (as__n + as__n), 0);
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_index.at( as__b) += 1; /* ¬a → b */
as__adj_index.at( as__a) += 1; /* ¬b → a */ }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_index.at(as__n + as__b) += 1; /* a → ¬b */
as__adj_index.at(as__n + as__a) += 1; /* b → ¬a */ }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_index.at( as__b) += 1; /* a → b */
as__adj_index.at(as__n + as__a) += 1; /* ¬b → ¬a */
as__adj_index.at(as__n + as__b) += 1; /* ¬a → ¬b */
as__adj_index.at( as__a) += 1; /* b → a */ }
// Initialize adjacency lists first elements indices.
as__index = 0;
for (as__i = 0; (as__n + as__n) > as__i; ++as__i) {
as__indeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__index;
as__index += as__indeg; }
// Scan incoming edges.
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_array.at(as__adj_index.at( as__b)) = as__n + as__a; /* ¬a → b */
as__adj_index.at( as__b) += 1;
as__adj_array.at(as__adj_index.at( as__a)) = as__n + as__b; /* ¬b → a */
as__adj_index.at( as__a) += 1; }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_array.at(as__adj_index.at(as__n + as__b)) = as__a; /* a → ¬b */
as__adj_index.at(as__n + as__b) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__a)) = as__b; /* b → ¬a */
as__adj_index.at(as__n + as__a) += 1; }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_array.at(as__adj_index.at( as__b)) = as__a; /* a → b */
as__adj_index.at( as__b) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__a)) = as__n + as__b; /* ¬b → ¬a */
as__adj_index.at(as__n + as__a) += 1;
as__adj_array.at(as__adj_index.at(as__n + as__b)) = as__n + as__a; /* ¬a → ¬b */
as__adj_index.at(as__n + as__b) += 1;
as__adj_array.at(as__adj_index.at( as__a)) = as__b; /* b → a */
as__adj_index.at( as__a) += 1; }
// Scan indegrees.
std::fill(as__adj_index.begin(), as__adj_index.begin() + (as__n + as__n), 0);
for (as__i = as__white_start; as__white___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 0”, a ∨ b */
as__adj_index.at( as__b) += 1; /* ¬a → b */
as__adj_index.at( as__a) += 1; /* ¬b → a */ }
for (as__i = as__red_start; as__red___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 1”, ¬a ∨ ¬b */
as__adj_index.at(as__n + as__b) += 1; /* a → ¬b */
as__adj_index.at(as__n + as__a) += 1; /* b → ¬a */ }
for (as__i = as__purple_start; as__purple___end > as__i; ++as__i) {
as__edges_array.at(as__i).assign_to(as__a, as__b); /* “a b 2”, (¬a ∨ b) ∧ (a ∨ ¬b) */
as__adj_index.at( as__b) += 1; /* a → b */
as__adj_index.at(as__n + as__a) += 1; /* ¬b → ¬a */
as__adj_index.at(as__n + as__b) += 1; /* ¬a → ¬b */
as__adj_index.at( as__a) += 1; /* b → a */ }
// Initialize adjacency lists first elements indices.
as__index = 0;
for (as__i = 0; (as__n + as__n) > as__i; ++as__i) {
as__indeg = as__adj_index.at(as__i);
as__adj_index.at(as__i) = as__index;
as__index += as__indeg; }
// Initialize one past end node’s sentinel.
as__adj_index.at(as__n + as__n) = as__index; }
/* Rao Kosaraju’s algorithm, strongly connected components, step 2. */ {
size_t const as__n = arg__problem.idm__n;
std::vector<uint32_t> const & as__kosajaru_list = arg__problem.idm__kosaraju_list;
std::vector<uint8_t> & as__visited = arg__problem.idm__visited;
std::fill(as__visited.begin(), as__visited.begin() + (as__n + as__n), 0);
ContextForDfsOnIncomingEdges as__ctx;
as__ctx.idm__adj_index = &arg__problem.idm__adj_index;
as__ctx.idm__adj_array = &arg__problem.idm__adj_array;
as__ctx.idm__visited = &arg__problem.idm__visited;
as__ctx.idm__scc_indicator = &arg__problem.idm__scc_indicator;
as__ctx.idm__scc_current = 0;
size_t as__t = 0; uint32_t as__i = 0;
for (as__t = 0; (as__n + as__n) > as__t; ++as__t) {
as__i = as__kosajaru_list.at(as__t);
if (0 == as__visited.at(as__i)) {
dfs_on_incoming_edges (as__ctx, as__i);
as__ctx.idm__scc_current += 1; }}}
/* Solve the 2SAT, already. */ {
arg__problem.idm__partition.swap(arg__problem.idm__visited); /* Repurposing memory. */
size_t const as__n = arg__problem.idm__n;
std::vector<uint32_t> const & as__scc_indicator = arg__problem.idm__scc_indicator;
std::vector<uint8_t> & as__partition = arg__problem.idm__partition;
size_t as__i = 0; uint32_t as__scc_i = 0; uint32_t as__scc_j = 0;
for (as__i = 0; as__n > as__i; ++as__i) {
as__scc_i = as__scc_indicator.at( as__i); /* SCC[i] */
as__scc_j = as__scc_indicator.at(as__n + as__i); /* SCC[¬i] */
if (as__scc_i == as__scc_j) {
throw std::invalid_argument("No assignment may satisfy all the given constraints."); }
as__partition.at(as__i) = ((as__scc_j < as__scc_i) ? 1 : 0); }}
}
void write_the_partition (Problem & arg__problem) {
std::ofstream as__os("andrei.out");
std::vector<uint8_t> const & as__partition = arg__problem.idm__partition;
size_t const as__n = arg__problem.idm__n;
size_t as__i = 0; uint32_t as__p = 0;
as__p = as__partition.at(0); as__os << as__p;
for (as__i = 1; as__n > as__i; ++as__i) {
as__p = as__partition.at(as__i); as__os << ' ' << as__p; }
as__os << '\n';
}
void demo (void) {
Problem as__problem;
read_the_graph (as__problem);
partition_the_nodes (as__problem);
write_the_partition (as__problem);
}
int main (void) {
int status = 19;
try {
demo();
status = 0; }
catch (std::runtime_error const & exc) {
(void) exc;
status = 23; }
catch (std::invalid_argument const & exc) {
(void) exc;
status = 17; }
catch (std::out_of_range const & exc) {
(void) exc;
status = 13; }
catch ( ... ) {
status = 19; }
return status;
}
