Submission #1799826

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef long long lint;
typedef pair< int, int > pii;
template< typename T > using Vec = vector< T >;

class UnionFind {
private:
	Vec< int > data;
	int num_of_g;
	
public:
	UnionFind(int n) : data(n, -1), num_of_g(n) {}
	
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		
		if (x == y) return 0;
		
		if (data[y] < data[x]) swap(x, y);
		data[x] += data[y]; data[y] = x;
		--num_of_g;
		
		return 1;
	}
	
	bool sameSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
	int getNumOfG() { return num_of_g; }
};

struct Edge {
	int u, v; lint c;
	bool flag;
	bool operator > (const Edge& e) const { return c > e.c; }
	lint posEncode() const { return ((lint)u << 32) | (lint)v; }
	lint negEncode() const { return ((lint)v << 32) | (lint)u; }
};

int main() {
	int N, Q;
	cin >> N >> Q;
	
	UnionFind uf(N);
	priority_queue< Edge, Vec< Edge >, greater< Edge > > que;
	for_(i,0,Q) {
		int A, B; lint C;
		cin >> A >> B >> C;
		que.push(Edge{A, B, C, true});
	}
	
	lint ans = 0;
	unordered_set< lint > zigzag_set;
	while (uf.getNumOfG() > 1) {
		Edge e = que.top(); que.pop();
		if (zigzag_set.count(e.posEncode()) || zigzag_set.count(e.negEncode())) continue;
		if (!uf.sameSet(e.u, e.v)) {
			zigzag_set.insert(e.posEncode());
			zigzag_set.insert(e.negEncode());
			uf.unionSet(e.u, e.v);
			ans += e.c;
		}
		if (e.flag) que.push(Edge{(e.u+1)%N, e.v, e.c+1, false});
		else que.push(Edge{e.u, (e.v+1)%N, e.c+1, true});
	}
	cout << ans << endl;
}

Submission Info

Judge Result