Submission #994157

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

void precalc() {
}

const int maxn = (int) 4e5 + 10;
int edges[maxn][3];

int n, q;

int read() {
  if (scanf("%d%d", &n, &q) < 2) {
    return 0;
  }
  for (int i = 0; i < q; ++i) {
    int s, t, c;
    scanf("%d%d%d", &s, &t, &c);
    edges[2 * i][0] = s, edges[2 * i][1] = t, edges[2 * i][2] = c;
    edges[2 * i + 1][0] = s + 1, edges[2 * i + 1][1] = t, edges[2 * i + 1][2] = c + 1;
  }
  q *= 2;
  return 1;
}


int pr[maxn], w[maxn];

int get(int v) {
  return pr[v] == v ? v : pr[v] = get(pr[v]);
}

void myUnion(int s, int t) {
  s = get(s), t = get(t);
  if (s == t) {
    return;
  }

  if (w[s] == w[t]) {
    ++w[s];
  }

  if (w[s] < w[t]) {
    swap(s, t);
  }

  pr[t] = s;
}

void solve() {
  for (int i = 0; i < n; ++i) {
    pr[i] = i;
    w[i] = 0;
  }

  set<pair<int, int> > evs;
  for (int i = 0; i < q; ++i) {
    evs.insert(mp(edges[i][2], i));
  }

  long long res = 0;
  while (sz(evs)) {
    int id = evs.begin()->second;
    evs.erase(evs.begin());
    int &s = edges[id][0], &t = edges[id][1];
    if (get(s) == get(t)) {
      continue;
    }
    myUnion(s, t);
    res += edges[id][2];
    s = (s + 1) % n;
    t = (t + 1) % n;
    edges[id][2] += 2;
    evs.insert(mp(edges[id][2], id));
  }
  printf("%lld\n", res);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:47:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &s, &t, &c);
                                ^

Judge Result