Submission #4541717


Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
#define int long long
const int N = 1e6 + 233;
const int M = N * 4;
struct E {
    int from, to, w;
}e[M]; int e_cnt = 0;

int n, q, inf, pre[N], suf[N];

inline void link(int x, int y, int w) {
    if (w == inf) return ;
    // cout << x - 1 << " " << y - 1 << " " << w << "\n";
    e[++e_cnt] = (E) {x, y, w};
}

namespace dsu {
    int pre[N];
    inline int find(int x) {
	return pre[x] == x ? x : pre[x] = find(pre[x]);
    }
    inline void init(int n) {
	rep (i, n) pre[i] = i;
    }
    inline void make(int x, int y) {
	pre[find(x)] = find(y);
    }
}

inline void doit() {
    sort(e + 1, e + e_cnt + 1, [](E a, E b) {
				   return a.w < b.w;
			       });
    dsu::init(n);
    int ans = 0;
    rep (i, e_cnt) {
	int fx = dsu::find(e[i].from);
	int fy = dsu::find(e[i].to);
	if (fx != fy) {
	    ans += e[i].w;
	    dsu::make(fx, fy);
	}
    }
    cout << ans << "\n";
}

signed main(void) {
    read(n); read(q);
    memset(pre, 38, sizeof pre);
    memset(suf, 38, sizeof suf);
    inf = pre[0];
    rep (i, q) {
	int x, y, w; read(x); read(y); read(w);
	++x; ++y;
	link(x, y, w);
	// if (x < y) {
	pre[x] = min(pre[x], w + 1);
	pre[y] = min(pre[y], w + 2);
	// } else {
	//     pre[x] = min(pre[x], w + 2);
	//     pre[y] = min(pre[y], w + 1);
	// }
    }
    for (int i = 1; i <= n + n; i++) {
	pre[i] = min(pre[i], pre[i - 1] + 2);
    }
    // for (int i = n + n; i >= 1; i--) {
    // 	suf[i] = min(suf[i], suf[i + 1] + 2);
    // }
    // for (int i = 1; i <= n + n; i++)
    // 	cout << pre[i] << " \n"[i == n + n];
    for (int i = 1; i <= n + n - 1; i++) {
	int x = i, y = i + 1;
	if (x > n) x -= n;
	if (y > n) y -= n;
	link(x, y, pre[i]);
	// link(x, y, suf[i + 1]);
    }
    doit();
}

Submission Info

Submission Time
Task G - Zigzag MST
User foreverpiano
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 2325 Byte
Status AC
Exec Time 100 ms
Memory 36480 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 6 ms 18688 KB
01-02.txt AC 48 ms 22784 KB
01-03.txt AC 93 ms 34688 KB
01-04.txt AC 37 ms 29824 KB
01-05.txt AC 25 ms 29056 KB
01-06.txt AC 31 ms 29312 KB
01-07.txt AC 40 ms 30720 KB
01-08.txt AC 52 ms 30592 KB
01-09.txt AC 41 ms 30464 KB
01-10.txt AC 68 ms 32512 KB
01-11.txt AC 78 ms 29696 KB
01-12.txt AC 99 ms 34560 KB
01-13.txt AC 99 ms 34560 KB
01-14.txt AC 100 ms 34560 KB
01-15.txt AC 98 ms 34560 KB
01-16.txt AC 98 ms 34560 KB
01-17.txt AC 98 ms 34560 KB
01-18.txt AC 64 ms 34432 KB
01-19.txt AC 29 ms 28544 KB
01-20.txt AC 33 ms 30464 KB
01-21.txt AC 48 ms 30464 KB
01-22.txt AC 72 ms 34560 KB
01-23.txt AC 72 ms 34560 KB
01-24.txt AC 25 ms 30336 KB
01-25.txt AC 79 ms 36480 KB
01-26.txt AC 32 ms 28032 KB
01-27.txt AC 29 ms 29312 KB
01-28.txt AC 79 ms 32512 KB
01-29.txt AC 74 ms 29824 KB
01-30.txt AC 97 ms 34560 KB
sample-01.txt AC 6 ms 18688 KB
sample-02.txt AC 6 ms 18688 KB
sample-03.txt AC 6 ms 18688 KB