Submission #7952817

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;
typedef pair<llint, P> E;

struct SegTree{
	int size;
	vector<llint> seg;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++) seg[i] = inf;
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = min(seg[i*2], seg[i*2+1]);
		}
	}

	llint query(int a, int b, int k, int l, int r)
	{
		if(b < l || r < a) return inf;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return min(lval, rval);
	}
	llint query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n, Q;
llint a[200005], b[200005], c[200005];
vector<E> vec;
SegTree seg(19);
UnionFind uf(200005);

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> Q;
	for(int i = 1; i <= Q; i++) cin >> a[i] >> b[i] >> c[i];
	
	seg.init();
	for(int i = 1; i <= Q; i++){
		llint u = a[i], v = b[i], w = c[i];
		if(u > v) v += n;
		
		llint val = seg.query(u, u); 
		seg.update(u, min(val, w-2*(u-1)-1));
		u += n;
		val = seg.query(u, u); 
		seg.update(u, min(val, w-2*(u-1)-1));
		
		val = seg.query(v, v); 
		seg.update(v, min(val, w-2*(v-1)));
		v += n;
		if(v < 2*n){
			val = seg.query(v, v); 
			seg.update(v, min(val, w-2*(v-1)));
		}
	}
	
	for(int i = 1; i <= Q; i++) vec.push_back(make_pair(c[i], make_pair(a[i], b[i])));
	for(int i = 0; i < n; i++){
		llint mn = seg.query(0, i) + 2*i;
		mn = min(mn, seg.query(0, n+i) + 2*(n+i));
		vec.push_back(make_pair(mn, make_pair(i, (i+1)%n)));
	}
	sort(vec.begin(), vec.end());
	
	llint ans = 0;
	for(int i = 0; i < vec.size(); i++){
		llint w = vec[i].first, u = vec[i].second.first, v = vec[i].second.second;
		if(uf.same(u, v)) continue;
		ans += w;
		uf.unite(u, v);
	}
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result