Submission #7475603

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200005, INF = 2000000000;
int n, Q, pre_tag[N], suf_tag[N], fa[N];
struct edge {
	int u, v, w;
};
bool operator<(const edge &a, const edge &b) {
	return a.w < b.w;
}

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

int main() {
	scanf("%d%d", &n, &Q);
	for (int i = 0; i < n; ++i)
		pre_tag[i] = suf_tag[i] = INF;
	vector<edge> e;
	for (int i = 1; i <= Q; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		suf_tag[a] = min(suf_tag[a], c - 2 * a + 1);
		pre_tag[a] = min(pre_tag[a], c + 2 * (n - a) + 1);
		suf_tag[b] = min(suf_tag[b], c - 2 * b + 2);
		pre_tag[b] = min(pre_tag[b], c + 2 * (n - b) + 2);
		e.push_back((edge){a, b, c});
	}
	for (int i = 1; i < n; ++i)
		suf_tag[i] = min(suf_tag[i], suf_tag[i - 1]);
	for (int i = n - 2; i >= 0; --i)
		pre_tag[i] = min(pre_tag[i], pre_tag[i + 1]);
	for (int i = 0; i < n; ++i)
		e.push_back({i, (i + 1) % n, min(suf_tag[i], pre_tag[i]) + 2 * i});
	sort(e.begin(), e.end());
	for (int i = 0; i < n; ++i)
		fa[i] = i;
	long long ans = 0;
	for (const auto &p : e) {
		int s = find(p.u), t = find(p.v);
		if (s != t)
			fa[s] = t, ans += p.w;
	}
	printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:18:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
                       ^
./Main.cpp:24:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^

Judge Result