Submission #6357168


Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define LL long long
#define RG register

using namespace std;
template<class T> inline void read(T &x) {
	x = 0; RG char c = getchar(); bool f = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
	x = f ? -x : x;
	return ;
}
template<class T> inline void write(T x) {
	if (!x) {putchar(48);return ;}
	if (x < 0) x = -x, putchar('-');
	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 200010;
struct Edge {
	int u, v, w;
	bool operator < (const Edge &z) const {
		return w < z.w;
	}
}e[N << 1];
int n, q, c, w[N], fa[N];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
 main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	read(n), read(q);
	int tot = 0;
	memset(w, 127, sizeof(w));
	for (int i = 1, x, y, z; i <= q; i++) {
		read(x), read(y), read(z);
		e[++tot] = (Edge) {x, y, z};
		w[x] = min(w[x], z + 1); w[y] = min(w[y], z + 2);
	}
	for (int i = 0; i < n; i++) w[i] = min(w[i], w[(i - 1 + n) % n] + 2);
	for (int i = 0; i < n; i++) w[i] = min(w[i], w[(i - 1 + n) % n] + 2);
	for (int i = 0; i < n; i++) e[++tot] = (Edge) {i, (i + 1) % n, w[i]};
	sort(e + 1, e + 1 + tot);
	for (int i = 0; i < n; i++) fa[i] = i;
	int ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = find(e[i].u), v = find(e[i].v);
		if (u == v) continue;
		ans += e[i].w;
		fa[v] = u;
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User luogu_bot5
Language C++ (GCC 5.4.1)
Score 1300
Code Size 1582 Byte
Status AC
Exec Time 85 ms
Memory 12800 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 2816 KB
01-02.txt AC 43 ms 6912 KB
01-03.txt AC 80 ms 12800 KB
01-04.txt AC 25 ms 8448 KB
01-05.txt AC 18 ms 8448 KB
01-06.txt AC 21 ms 8448 KB
01-07.txt AC 19 ms 8448 KB
01-08.txt AC 19 ms 8448 KB
01-09.txt AC 22 ms 8448 KB
01-10.txt AC 48 ms 10496 KB
01-11.txt AC 66 ms 9728 KB
01-12.txt AC 78 ms 12672 KB
01-13.txt AC 77 ms 12800 KB
01-14.txt AC 77 ms 12800 KB
01-15.txt AC 80 ms 12800 KB
01-16.txt AC 77 ms 12800 KB
01-17.txt AC 77 ms 12800 KB
01-18.txt AC 63 ms 12800 KB
01-19.txt AC 19 ms 8448 KB
01-20.txt AC 19 ms 8448 KB
01-21.txt AC 32 ms 10496 KB
01-22.txt AC 62 ms 12800 KB
01-23.txt AC 62 ms 12800 KB
01-24.txt AC 19 ms 8448 KB
01-25.txt AC 85 ms 12800 KB
01-26.txt AC 25 ms 8448 KB
01-27.txt AC 24 ms 8448 KB
01-28.txt AC 53 ms 12544 KB
01-29.txt AC 64 ms 11904 KB
01-30.txt AC 75 ms 12800 KB
sample-01.txt AC 2 ms 2816 KB
sample-02.txt AC 2 ms 2816 KB
sample-03.txt AC 2 ms 2816 KB