Submission #2303337

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

using taplis=tuple<int,int,int>;
struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};
int N,Q;

signed main(){
    cin>>N>>Q;

    priority_queue<taplis,vector<taplis>,greater<taplis>>que;
    rep(i,Q){
        int a,b,c;
        cin>>a>>b>>c;
        que.push(make_tuple(c,a,b));
    }

    UnionFindTree uf(N);
    int ans=0;
    while(que.size()){
        int c,a,b;
        tie(c,a,b)=que.top();
        que.pop();
        if(b==-1){
            if(uf.areSame(a,(a+1)%N));
            else{
                uf.unite(a,(a+1)%N);
                ans+=c;
                que.push(make_tuple(c+2,(a+1)%N,-1));
            }
        }
        else{
            if(!uf.areSame(a,b)){
                uf.unite(a,b);
                ans+=c;
            }
            que.push(make_tuple(c+1,a,-1));
            que.push(make_tuple(c+2,b,-1));
        }
    }
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result