Submission #6133638


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int u[maxn];
int find(int x){
	if(x == u[x]) return x;
	return u[x] = find(u[x]);
}
long long cost[maxn];
int main(){
	iota(u, u + maxn, 0);
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++) cost[i] = 1ll<<60;
	vector<tuple<int,int,int> > ed;
	for(int i = 0; i < q; i++){
		int a, b; long long c; cin >> a >> b >> c;
		cost[a] = min(cost[a], c + 1);
		cost[b] = min(cost[b], c + 2);
		ed.push_back(make_tuple(c, a, b));
	}
	for(int i = 0; i < 2 * n; i++){
		int now = i % n; 
		int prv = now - 1; if(prv < 0) prv += n;
		cost[now] = min(cost[now], cost[prv] + 2);
	}
	for(int i = 0; i < n; i++) ed.push_back(make_tuple(cost[i], i, (i + 1) % n));
	sort(ed.begin(), ed.end());
	long long ans = 0;
	for(auto e : ed){
		int w, x, y; tie(w, x, y) = e;
		if(find(x) != find(y)){
			ans += w;
			u[find(x)] = find(y);
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User FMota
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 966 Byte
Status AC
Exec Time 252 ms
Memory 11628 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 36
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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 1024 KB
01-02.txt AC 163 ms 4212 KB
01-03.txt AC 243 ms 10864 KB
01-04.txt AC 25 ms 7408 KB
01-05.txt AC 17 ms 6128 KB
01-06.txt AC 21 ms 6644 KB
01-07.txt AC 21 ms 5748 KB
01-08.txt AC 24 ms 5748 KB
01-09.txt AC 37 ms 5748 KB
01-10.txt AC 138 ms 10480 KB
01-11.txt AC 229 ms 8816 KB
01-12.txt AC 247 ms 9840 KB
01-13.txt AC 252 ms 9712 KB
01-14.txt AC 247 ms 9584 KB
01-15.txt AC 248 ms 10480 KB
01-16.txt AC 245 ms 9200 KB
01-17.txt AC 250 ms 9840 KB
01-18.txt AC 221 ms 11500 KB
01-19.txt AC 20 ms 7156 KB
01-20.txt AC 33 ms 5748 KB
01-21.txt AC 85 ms 5748 KB
01-22.txt AC 232 ms 9968 KB
01-23.txt AC 208 ms 9328 KB
01-24.txt AC 28 ms 8304 KB
01-25.txt AC 240 ms 11628 KB
01-26.txt AC 27 ms 8304 KB
01-27.txt AC 39 ms 6768 KB
01-28.txt AC 166 ms 10480 KB
01-29.txt AC 234 ms 9840 KB
01-30.txt AC 249 ms 10224 KB
sample-01.txt AC 2 ms 1024 KB
sample-02.txt AC 2 ms 1024 KB
sample-03.txt AC 2 ms 1024 KB