Submission #994551

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
struct unifnd{
  VI ht,pr;
  in fnd(in a){
    in ta=a;
    while(a!=pr[a])a=pr[a];
    in tt=ta;
    while(ta!=a){
      tt=pr[ta];
      pr[ta]=a;
      ta=tt;
    }
    return a;
  }
  void uni(in a, in b){
    a=fnd(a);
    b=fnd(b);
    if(a==b)return;
    if(ht[b]<ht[a])swap(a,b);
    pr[a]=b;
    ht[b]+=(ht[a]==ht[b]);
  }
  void ini(in n){
    ht.resize(n);
    pr.resize(n);
    forn(i,n){
      ht[i]=0;
      pr[i]=i;
    }
  }
};
unifnd tfd;
VI a,b,c;
struct cand{
  in id;
  cand(in z=0){
    id=z;
  }
  bool operator<(const cand cp)const{
    return c[id]>c[cp.id];
  }
};
priority_queue<cand> q;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,qq;
  cin>>n>>qq;
  tfd.ini(n);
  in sm=0;
  in ta,tb,tc;
  forn(z,qq){
    cin>>ta>>tb>>tc;
    a.PB(ta%n);
    b.PB(tb%n);
    c.PB(tc);
    a.PB((ta+1)%n);
    b.PB(tb%n);
    c.PB(tc+1);
    q.push(cand(2*z));
    q.push(cand(2*z+1));
  }
  in u;
  while(!q.empty()){
    u=q.top().id;
    q.pop();
    if(tfd.fnd(a[u])==tfd.fnd(b[u]))
      continue;
    tfd.uni(a[u],b[u]);
    sm+=c[u];
    a[u]=(a[u]+1)%n;
    b[u]=(b[u]+1)%n;
    c[u]+=2;
    q.push(cand(u));
  }
  cout<<sm<<endl;
  return 0;
}

Submission Info

Judge Result