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
AC × 3
AC × 33
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