Cod sursa(job #2791409)
| Utilizator |  Marius B mgnt |
Data | 30 octombrie 2021 14:28:01 |
|---|---|---|---|
| Problema | Andrei | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 27.83 kb |
#include <fstream>
#include <cstddef>
#include <vector>
#include <algorithm>
#include <numeric>
struct Edge {
uint32_t idm__u;
uint32_t idm__v;
inline void assign (uint32_t arg__a, uint32_t arg__b) noexcept {
idm__u = std::min(arg__a, arg__b);
idm__v = std::max(arg__a, arg__b); }
bool operator < (Edge const & arg__other) const noexcept {
return (idm__u == arg__other.idm__u) ? (idm__v < arg__other.idm__v)
: (idm__u < arg__other.idm__u); }
};
struct Problem {
size_t idm__n; // idm, instance data member
size_t idm__m;
size_t idm__h;
size_t idm__k;
std::vector<Edge> idm__E;
std::vector<size_t> idm__J;
std::vector<uint32_t> idm__A;
std::vector<uint32_t> idm__Q;
std::vector<uint8_t> idm__P;
Problem (void) {
idm__n = 0; idm__m = 0; idm__k = 0; idm__k = 0; }
};
void dfs__group_nodes (Problem & arg__problem, uint32_t arg__q, size_t arg__x) {
/// The DFS grouping nodes connected by purple edges.
arg__problem.idm__Q.at(arg__x) = arg__q;
size_t as__begin = arg__problem.idm__J.at(arg__x + 0); // as, automatic storage (duration)
size_t as__end = arg__problem.idm__J.at(arg__x + 1);
size_t as__i = 0;
for (as__i = as__begin; as__end > as__i; ++as__i) {
if (arg__problem.idm__Q.at(arg__problem.idm__A.at(as__i)) != arg__q) {
dfs__group_nodes(arg__problem, arg__q, arg__problem.idm__A.at(as__i)); }}
}
void dfs__bipartition (Problem & arg__problem, uint8_t arg__p, size_t arg__x) {
/// The DFS partitioning nodes in the two partitions of the bipartite graph.
arg__problem.idm__P.at(arg__x) = arg__p;
size_t as__begin = arg__problem.idm__J.at(arg__x + 0);
size_t as__end = arg__problem.idm__J.at(arg__x + 1);
size_t as__i = 0;
for (as__i = as__begin; as__end > as__i; ++as__i) {
if (arg__problem.idm__P.at(arg__problem.idm__A.at(as__i)) == arg__p) {
throw std::invalid_argument("Invalid edge!"); }
if (arg__problem.idm__P.at(arg__problem.idm__A.at(as__i)) == 2) {
dfs__bipartition(arg__problem, 1 - arg__p, arg__problem.idm__A.at(as__i)); }}
}
void build_adjacencies (Problem & arg__problem, size_t arg__begin, size_t arg__end) {
// Sort edges; this is supports filtering out duplicated edges.
std::vector<Edge> & as__E = arg__problem.idm__E;
std::sort(as__E.begin() + arg__begin, as__E.begin() + arg__end);
// Filter out duplicate edges.
size_t as__end2 = arg__begin;
size_t as__i = 0;
for (as__i = arg__begin + 1; arg__end > as__i; ++as__i) {
if (as__E.at(as__end2) < as__E.at(as__i)) {
if ((as__end2 + 1) != as__i) {
as__E.at(as__end2 + 1) = as__E.at(as__i); }
++as__end2; }}
if (as__end2 < arg__end) {
++as__end2; }
// Count how many edges are adjacent with each node.
size_t const as__n = arg__problem.idm__n;
std::vector<size_t> & as__J = arg__problem.idm__J;
std::fill(as__J.begin(), as__J.begin() + as__n, 0);
for (as__i = arg__begin; as__end2 > as__i; ++as__i) {
as__J.at(as__E.at(as__i).idm__u) += 1;
as__J.at(as__E.at(as__i).idm__v) += 1; }
// Determine from which index to store neighbours, for each node.
size_t as__pos = 0; size_t as__count = 0;
for (as__i = 0; as__n > as__i; ++ as__i) {
as__count = as__J.at(as__i); as__J.at(as__i) = as__pos; as__pos += as__count; }
// Put the neighbours in the adjacency lists.
std::vector<uint32_t> & as__A = arg__problem.idm__A;
for (as__i = arg__begin; as__end2 > as__i; ++as__i) {
as__A.at(as__J.at(as__E.at(as__i).idm__u)) = as__E.at(as__i).idm__v;
as__A.at(as__J.at(as__E.at(as__i).idm__v)) = as__E.at(as__i).idm__u;
as__J.at(as__E.at(as__i).idm__u) += 1;
as__J.at(as__E.at(as__i).idm__v) += 1; }
// Count how many edges are adjacent with each node.
std::fill(as__J.begin(), as__J.begin() + as__n, 0);
for (as__i = arg__begin; as__end2 > as__i; ++as__i) {
as__J.at(as__E.at(as__i).idm__u) += 1;
as__J.at(as__E.at(as__i).idm__v) += 1; }
// Determine from which index the neighbours were stored, for each node.
as__pos = 0; as__count = 0;
for (as__i = 0; as__n > as__i; ++ as__i) {
as__count = as__J.at(as__i); as__J.at(as__i) = as__pos; as__pos += as__count; }
// Also determine for the 'end' node, a sentinel.
as__J.at(as__n) = as__pos;
}
void group_the_nodes_connected_by_purple_edges (Problem & arg__problem) {
/// It groups together with all neighbours (by purple edges), each not yet grouped node.
size_t const as__m = arg__problem.idm__m;
size_t const as__k = arg__problem.idm__k;
build_adjacencies(arg__problem, as__m - as__k, as__m);
size_t const as__n = arg__problem.idm__n;
std::vector<uint32_t> & as__Q = arg__problem.idm__Q;
uint32_t as__r = 0; size_t as__i = 0;
for (as__i = as__r = 0; as__n > as__i; ++as__i, ++as__r) {
as__Q.at(as__i) = as__r; }
for (as__i = as__r = 0; as__n > as__i; ++as__i, ++as__r) {
if (as__Q.at(as__i) == as__r) {
dfs__group_nodes(arg__problem, as__r, as__i); }}
}
void relabel_the_white_and_red_edges (Problem & arg__problem) {
/// It relabels white and red edges accounting how nodes were grouped on their purple edges.
std::vector<uint32_t> & as__Q = arg__problem.idm__Q;
std::vector<Edge> & as__E = arg__problem.idm__E;
size_t const as__h = arg__problem.idm__h; size_t as__i = 0;
for (as__i = 0; as__h > as__i; ++as__i) {
as__E.at(as__i).idm__u = as__Q.at(as__E.at(as__i).idm__u);
as__E.at(as__i).idm__v = as__Q.at(as__E.at(as__i).idm__v);
if (as__E.at(as__i).idm__u == as__E.at(as__i).idm__v) {
throw std::invalid_argument("Invalid edge."); }}
}
void check_that_the_simplified_graph_is_bipartite (Problem & arg__problem) {
/// It checks that the simplified graph is bipartite, by building its partitions A and B.
build_adjacencies(arg__problem, 0, arg__problem.idm__h);
std::vector<uint32_t> & as__Q = arg__problem.idm__Q;
std::vector<uint8_t> & as__P = arg__problem.idm__P;
size_t const as__n = arg__problem.idm__n;
size_t as__i = 0; uint32_t as__r = 0;
for (as__i = 0, as__r = 0; as__n > as__i; ++as__i, ++as__r) {
as__P.at(as__i) = (as__Q.at(as__i) == as__r) ? 2 : 3; }
for (as__i = 0; as__n > as__i; ++as__i) {
if (as__P.at(as__i) == 2) {
dfs__bipartition (arg__problem, 0, as__i); }}
}
void color_each_group_of_nodes_connected_by_purple_edges (Problem & arg__problem) {
/// Puts the color to all nodes in the group, for each node in the simplified graph.
std::vector<uint32_t> & as__Q = arg__problem.idm__Q;
std::vector<uint8_t> & as__P = arg__problem.idm__P;
size_t const as__n = arg__problem.idm__n;
size_t as__i = 0; uint32_t as__r = 0;
for (as__i = 0, as__r = 0; as__n > as__i; ++as__i, ++as__r) {
if (as__Q.at(as__i) != as__r) {
as__P.at(as__i) = as__P.at(as__Q.at(as__i)); }}
}
void read_the_graph (Problem & arg__problem) {
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::invalid_argument("Invalid graph size."); }
if (std::numeric_limits<size_t>::max() - 1 < as__n) {
throw std::runtime_error("Implementation limit. As if."); }
if (std::numeric_limits<size_t>::max() - as__m < as__m) {
throw std::runtime_error("Implementation limit. As if."); }
std::vector<uint8_t> as__P(as__n);
std::vector<uint32_t> as__Q(as__n);
std::vector<size_t> as__J(as__n + 1);
std::vector<uint32_t> as__A(as__m + as__m);
std::vector<Edge> as__E(as__m);
size_t as__i = 0; uint32_t as__a = 0; uint32_t as__b = 0; uint32_t as__c = 0;
size_t as__h = 0; size_t as__k = 0;
for (as__i = 0; as__n > 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::invalid_argument("Invalid edge."); }
if ((as__a == as__b) && ((as__c == 0) || (as__c == 1))) {
throw std::invalid_argument("Invalid edge."); }
--as__a; --as__b;
if (2 == as__c) {
/* Purple. */
if (as__a != as__b) {
as__E.at((as__m - 1) - as__k).assign(as__a, as__b); ++as__k; }}
else {
/* White or Red. */ as__E.at(as__h).assign(as__a, as__b); ++as__h; }}
// Okay!
arg__problem.idm__n = as__n;
arg__problem.idm__m = as__m;
arg__problem.idm__h = as__h;
arg__problem.idm__k = as__k;
arg__problem.idm__E.swap(as__E);
arg__problem.idm__J.swap(as__J);
arg__problem.idm__A.swap(as__A);
arg__problem.idm__Q.swap(as__Q);
arg__problem.idm__P.swap(as__P);
}
void partition_the_nodes (Problem & arg__problem) {
group_the_nodes_connected_by_purple_edges (arg__problem);
relabel_the_white_and_red_edges (arg__problem);
check_that_the_simplified_graph_is_bipartite (arg__problem);
color_each_group_of_nodes_connected_by_purple_edges (arg__problem);
}
void write_the_partition (Problem & arg__problem) {
std::ofstream as__os("andrei.out");
std::vector<uint8_t> const & as__P = arg__problem.idm__P;
size_t const as__n = arg__problem.idm__n; size_t as__i = 0;
as__os << static_cast<uint32_t>(as__P.at(0));
for (as__i = 1; as__n > as__i; ++as__i) {
as__os << ' ' << static_cast<uint32_t>(as__P.at(as__i)); }
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::invalid_argument const & exc ) {
(void) exc;
status = 17; }
catch ( ... ) {
status = 19; }
return status;
}
