Submission #993638

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 4e5 + 100;
vector <pair <int, int> > g[N];
int par[N];
int sz[N];

int getP(int x)
{
	if (par[x] == x) return x;
	return par[x] = getP(par[x] );
}

bool add(int a, int b)
{
	a = getP(a);
	b = getP(b);
	if (a == b) return false;
	if (sz[a] > sz[b] )
	{
		sz[a] += sz[b];
		par[b] = a;
	}
	else
	{
		sz[b] += sz[a];
		par[a] = b;
	}
	return true;
}
int a[N], b[N], c[N];

int main(int,  char **)
{
#ifdef LOCAL
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n, q;
	scanf("%d%d", &n, &q);
	
	for (int i = 0; i < n; i++)
	{
		sz[i] = 1;
		par[i] = i;
	}

	int minC = (int) 1e9 + 100;
	for (int i = 0; i < q; i++)
	{
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		minC = min(minC, c[i] );
	}

	long long ans = (n - 1) * 1LL * minC;
	for (int i = 0; i < q; i++)
	{
		if (c[i] - minC > n) continue;
		g[c[i] - minC].emplace_back(a[i], b[i]);
		g[c[i] - minC + 1].emplace_back( (a[i] + 1) % n, b[i]);
	}
	
	for (int i = 0; i < N; i++)
	{
		for (auto p : g[i] )
		{
//			eprintf(">>> %d %d\n", p.first, p.second);
			if (add(p.first, p.second) )
			{
//				eprintf("%d : %d %d\n", i, p.first, p.second);
				ans += i;
				g[i + 2].emplace_back((p.first + 1) % n, (p.second + 1) % n);
			}
		}
	}

	printf("%lld\n", ans);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:61: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:72:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a[i], &b[i], &c[i]);
                                       ^

Judge Result