疑问+求助【玄二关】
查看原帖
疑问+求助【玄二关】
846041
__xxy_free_ioi__楼主2025/2/8 15:57

调了半天,发现我的代码吸氧就RE,不吸氧就AC,请问各位dalao这是为何?且我们作业在vjudge上交,如何在vjudge上提交时关闭O2?QAQ

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e6 + 10;

struct E {
	int a, b, w;
} e[N];

int n, m;
int fa[N], st[N], idx, h[N];
vector<pair<int, int>> g[N];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void join(int x, int y) {
	fa[find(x)] = find(y);
}

bool cmp(E x, E y) {
    if (h[x.b] != h[y.b]) return h[x.b] > h[y.b];
    return x.w < y.w;
}

int dfs(int u, long long& ans) {
	for (auto t : g[u]) {
	    int v = t.first, w = t.second;
	    e[++idx].a = u, e[idx].b = v, e[idx].w = w;
		if (st[v] == 0 && h[u] >= h[v]) {
			ans++;
			st[v] = 1;
			dfs(v, ans);
		}
	}
}

signed main() {
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
		fa[i] = i;
	}
	
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (h[a] >= h[b]) g[a].push_back({b, c});
		if (h[b] >= h[a]) g[b].push_back({a, c});
	}
	 
	long long res = 0, ans = 1;
	st[1] = 1;
	dfs(1, ans);
	m = idx;
	
	sort(e + 1, e + m + 1, cmp);
	
	for (int i = 1; i <= m; i++) {
		int a = e[i].a, b = e[i].b, w = e[i].w;
		if (find(a) != find(b)) {
			res += w;
			join(a, b);
		}
	}
	
	cout << ans << ' ' << res;
	
	return 0;
}
2025/2/8 15:57
加载中...