Submission #4418817

---

Source Code Expand

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int mod=1;
template<typename T=int>
T gi() {
    T x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
string to_string(string s) { return '"'+s+'"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b?"true":"false"); }
template<typename A,typename B> string to_string(pair<A,B> p) {
    return "("+to_string(p.fi)+","+to_string(p.se)+")";
}
template<typename T> string to_string(T v) {
    int fst=1;string ret="{";
    for(auto x:v) {
        if(!fst) ret+=",";
        fst=0,ret+=to_string(x);
    }
    ret+="}";return ret;
}
void dbg_out() { cerr<<endl; }
template<typename Head,typename... Tail> void dbg_out(Head H,Tail... T) {
    cerr<<" "<<to_string(H);
    dbg_out(T...);
}
#define dbg(...) cerr<<"{"<<#__VA_ARGS__<<"}:",dbg_out(__VA_ARGS__)

template<typename T>
int qpow(int a,T b) {
    int ret=1;
    while(b) {
        if(b&1) ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ret;
}

const int N=2e5+10;

int n,Q,f[N];
vector<tuple<int,int,int>> e;

namespace dsu {

    int fa[N];

    void init() {
        for(int i=1;i<=n;i++) fa[i]=i;
    }

    int getf(int x) {
        return x==fa[x]?x:fa[x]=getf(fa[x]);
    }

    bool merge(int x,int y) {
        x=getf(x),y=getf(y);
        if(x==y) return 0;
        fa[y]=x;return 1;
    }
    
}

int main() {
    n=gi(),Q=gi();
    memset(f,0x3f,sizeof(f));
    while(Q--) {
        int a=gi()+1,b=gi()+1,c=gi();
        chkmin(f[a],c+1),chkmin(f[b],c+2);
        e.pb(mt(c,a,b));
    }
    for(int i=2;i<=n;i++) chkmin(f[i],f[i-1]+2);
    chkmin(f[1],f[n]+2);
    for(int i=2;i<=n;i++) chkmin(f[i],f[i-1]+2);
    for(int i=1;i<=n;i++) e.pb(mt(f[i],i,i%n+1));
    dsu::init();
    sort(all(e));
    ll ans=0;
    for(auto x:e) {
        int u=get<1>(x),v=get<2>(x),w=get<0>(x);
        if(dsu::merge(u,v)) ans+=w;
    }
    printf("%lld\n",ans);
    return 0;
}

Submission Info

Judge Result