Submission #993558

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MX = 210000;
const int MAXN = 210000;

int n, q;
set<pair<int, int> > ss0;
set<pair<int, int> > ss1;
set<pair<int, int> > ss2;
int a[MAXN];
int b[MAXN];
ll c[MAXN];
vector<pair<int, int> > go[MX];
int p[MAXN];
int sz[MAXN];

int get(int a) {
	if (a == p[a])
		return a;
	return p[a] = get(p[a]);
}

int un(int a, int b) {
	a = get(a);
	b = get(b);
	if (a == b)
		return 0;
	if (sz[a] < sz[b])
		swap(a, b);
	sz[a] += sz[b];
	p[b] = a;
	return 1;
}

int main() {
	scanf("%d%d", &n, &q);
	ll mn = 1e9;
	for (int i = 0; i < q; ++i) {
		scanf("%d%d%lld", a + i, b + i, c + i);
		mn = min(mn, c[i]);
	}
	ll ans = mn * (n - 1);
	for (int i = 0; i < q; ++i)
		c[i] -= mn;
	for (int i = 0; i < q; ++i) {
		if (c[i] < MX)
			go[c[i]].push_back(make_pair(a[i], b[i]));
		if (c[i] + 1 < MX) {
			go[c[i] + 1].push_back(make_pair((a[i] + 1) % n, b[i]));
		}
	}
	for (int i = 0; i < n; ++i)
		p[i] = i, sz[i] = 1;
	for (int i = 0; i < MX; ++i) {
		for (auto j: go[i])
			ss0.insert(j);
		ss2.clear();
		for (auto j: ss0) {
			if (un(j.first, j.second))
				ss2.insert(make_pair((j.first + 1) % n, (j.second + 1) % n)), ans += i;
		}
		swap(ss0, ss2);
		swap(ss1, ss0);
	}
	cout << ans << "\n";
	return 0;
}

Submission Info

Compile Error

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

Judge Result