QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1510#881345#9904. 最小生成树TulipeNoirepaper_Success!2025-02-04 16:33:172025-02-04 16:41:23

详细

Extra Test:

Time Limit Exceeded

input:

200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#881345#9904. 最小生成树paper_97 1824ms7680kbC++141.1kb2025-02-04 15:02:152025-02-04 16:52:25

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 200010;
int a[N * 2], id[N * 2], fa[N];
bool cmp(int x, int y) { return a[x] < a[y]; }
static int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;cin >> n;
	for (int i = 3; i <= n * 2 - 1; i ++ ) cin >> a[i];
	for (int i = 3; i <= n * 2 - 1; i ++ ) id[i] = i;
	for (int i = 1; i <= n; i ++ ) fa[i] = i;
	sort(id + 3, id + n * 2, cmp);
	int num = 0;
	long long ans = 0;
	for (register int i = 3; i <= n * 2 + 1; i ++ ) {
		int u = id[i], ad = 0;
		for (register int j = max(1, u - n); j <= u / 2; j ++ ) {
			if (get(j) != get(u - j)) fa[get(j)] = get(u - j), ans += a[u], num ++, ad = -1e4;
			else ad ++;
			if (ad == 50) break;
		}
		u = id[i], ad = 0;
		for (register int j = u / 2; j >= max(1, u - n); j -- ) {
			if (get(j) != get(u - j)) fa[get(j)] = get(u - j), ans += a[u], num ++, ad = -1e4;
			else ad ++;
			if (ad == 50) break;
		}
		if (num == n - 1) break;
	}
	cout << ans;
	return 0;
}