Submission #992896

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll INF = (ll)2e9;
const int N = 500500;
int n, q;
int m;

struct Edge
{
	int v, u;
	ll w;

	Edge() : v(), u(), w() {}
	Edge (int _v, int _u, ll _w) : v(_v), u(_u), w(_w) {}

	bool operator < (const Edge &e) const
	{
		return w < e.w;
	}
};

Edge ed[N];
ll a[N];

int par[N];
int sz[N];

int getPar(int v)
{
	return (par[v] == -1 ? v : par[v] = getPar(par[v]));
}
bool unite(int v, int u)
{
	v = getPar(v);
	u = getPar(u);
	if (v == u) return false;
	if (sz[v] < sz[u]) swap(v, u);
	sz[v] += sz[u];
	par[u] = v;
	return true;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++)
		a[i] = INF;
	while(q--)
	{
		int v, u;
		ll w;
		scanf("%d%d%lld", &v, &u, &w);
		ed[m++] = Edge(v, u, w);
		a[v] = min(a[v], w + 1);
		a[u] = min(a[u], w + 2);
	}
	for (int k = 0; k < 2; k++)
	{
		a[0] = min(a[0], a[n - 1] + 2);
		for (int i = 1; i < n; i++)
			a[i] = min(a[i], a[i - 1] + 2);
	}
	for (int i = 0; i < n; i++)
		ed[m++] = Edge(i, (i + 1) % n, a[i]);
	sort(ed, ed + m);
	for (int i = 0; i < n; i++)
	{
		par[i] = -1;
		sz[i] = 1;
	}
	ll ans = 0;
	for (int i = 0; i < m; i++)
		if (unite(ed[i].v, ed[i].u))
			ans += ed[i].w;
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54: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:61:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld", &v, &u, &w);
                                ^

Judge Result