Submission #993465
Source Code Expand
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author RiaD
*/
#include <iostream>
#include <fstream>
#include <iostream>
#include <tuple>
#include <algorithm>
#include <set>
#include <iterator>
#include <string>
#include <stdexcept>
#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
if(!(condition)) { \
throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif
/**
* Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
* it's reference type is not a reference.
*
* It doesn't return reference because
* 1. Anyway it'll not satisfy requirement [forward.iterators]/6
* If a and b are both dereferenceable, then a == b if and only if *a and
* b are bound to the same object.
* 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
*
* Note, reverse_iterator is not guaranteed to work now too since it works only with bidirectional iterators,
* but it's seems to work at least on my implementation.
*
* It's not really useful anywhere except iterating anyway.
*/
template <typename T>
class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
public:
explicit IntegerIterator(T value): value(value) {
}
IntegerIterator& operator++() {
++value;
return *this;
}
IntegerIterator operator++(int) {
IntegerIterator copy = *this;
++value;
return copy;
}
IntegerIterator& operator--() {
--value;
return *this;
}
IntegerIterator operator--(int) {
IntegerIterator copy = *this;
--value;
return copy;
}
T operator*() const {
return value;
}
bool operator==(IntegerIterator rhs) const {
return value == rhs.value;
}
bool operator!=(IntegerIterator rhs) const {
return !(*this == rhs);
}
private:
T value;
};
template <typename T>
class IntegerRange {
public:
IntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin <= end);
}
IntegerIterator<T> begin() const {
return IntegerIterator<T>(begin_);
}
IntegerIterator<T> end() const {
return IntegerIterator<T>(end_);
}
private:
T begin_;
T end_;
};
template <typename T>
class ReversedIntegerRange {
typedef std::reverse_iterator<IntegerIterator<T>> IteratorType;
public:
ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin >= end);
}
IteratorType begin() const {
return IteratorType(IntegerIterator<T>(begin_));
}
IteratorType end() const {
return IteratorType(IntegerIterator<T>(end_));
}
private:
T begin_;
T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
return ReversedIntegerRange<T>(from + 1, to);
}
#include <vector>
#include <cstddef>
class DSU {
public:
explicit DSU(std::size_t n): dsu(n) {
for (std::size_t i = 0; i < n; ++i) {
dsu[i] = i;
}
}
std::size_t getSet(std::size_t v) {
SPCPPL_ASSERT(v < dsu.size());
if (v == dsu[v]) {
return v;
}
return dsu[v] = getSet(dsu[v]);
}
void unite(std::size_t u, std::size_t v) {
SPCPPL_ASSERT(u < dsu.size());
SPCPPL_ASSERT(v < dsu.size());
u = getSet(u);
v = getSet(v);
dsu[v] = u;
}
private:
std::vector<std::size_t> dsu;
};
#include <cassert>
using namespace std;
class TaskG {
public:
void solve(std::istream& in, std::ostream& out) {
int n, q;
in >> n >> q;
//set<pair<int, int>> used;
struct Edge{
int a, b, c;
bool operator < (const Edge& e) const {
return tie(c, a, b) < tie(e.c, e.a, e.b);
}
};
set<Edge> edges;
for (int i: range(q)) {
int a, b, c;
in >> a >> b >> c;
edges.insert({a, b, c});
edges.insert({b, (a + 1) % n, c + 1});
}
int comps = n;
DSU dsu(n);
int64_t ans = 0;
while (comps > 1) {
assert(!edges.empty());
Edge e = *edges.begin();
edges.erase(edges.begin());
//cerr << e.a << ' ' << e.b << ' ' << e.c << endl;
//if (.second) {
if (dsu.getSet(e.a) != dsu.getSet(e.b)) {
//cerr << e.a << ' ' << e.b << ' ' << e.c << endl;
--comps;
ans += e.c;
dsu.unite(e.a, e.b);
edges.insert({(e.a + 1) % n, (e.b + 1) % n, e.c + 2});
}
//}
}
out << ans << "\n";
}
};
int main() {
std::ios_base::sync_with_stdio(false);
TaskG solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
in.tie(nullptr);
out << std::fixed;
out.precision(20);
solver.solve(in, out);
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
riadwaw |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
5614 Byte |
Status |
AC |
Exec Time |
316 ms |
Memory |
26880 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
1300 / 1300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
256 KB |
01-02.txt |
AC |
210 ms |
25216 KB |
01-03.txt |
AC |
231 ms |
26880 KB |
01-04.txt |
AC |
16 ms |
1792 KB |
01-05.txt |
AC |
16 ms |
1792 KB |
01-06.txt |
AC |
19 ms |
1792 KB |
01-07.txt |
AC |
23 ms |
1792 KB |
01-08.txt |
AC |
27 ms |
1920 KB |
01-09.txt |
AC |
37 ms |
3072 KB |
01-10.txt |
AC |
128 ms |
14336 KB |
01-11.txt |
AC |
246 ms |
25984 KB |
01-12.txt |
AC |
255 ms |
26752 KB |
01-13.txt |
AC |
251 ms |
26880 KB |
01-14.txt |
AC |
266 ms |
26880 KB |
01-15.txt |
AC |
257 ms |
26880 KB |
01-16.txt |
AC |
268 ms |
26880 KB |
01-17.txt |
AC |
267 ms |
26880 KB |
01-18.txt |
AC |
71 ms |
1792 KB |
01-19.txt |
AC |
19 ms |
1792 KB |
01-20.txt |
AC |
35 ms |
2048 KB |
01-21.txt |
AC |
109 ms |
8960 KB |
01-22.txt |
AC |
316 ms |
26880 KB |
01-23.txt |
AC |
313 ms |
26880 KB |
01-24.txt |
AC |
26 ms |
3456 KB |
01-25.txt |
AC |
278 ms |
26880 KB |
01-26.txt |
AC |
17 ms |
1792 KB |
01-27.txt |
AC |
38 ms |
2944 KB |
01-28.txt |
AC |
196 ms |
17280 KB |
01-29.txt |
AC |
283 ms |
26112 KB |
01-30.txt |
AC |
308 ms |
26880 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |
sample-03.txt |
AC |
3 ms |
256 KB |