Submission #1112209

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fin "\n"

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

typedef tuple<int,int,LL> T;
typedef pair<int,int> P;


namespace _DSU{
#define SZ 200000
    int mem[2][SZ];
}
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
    }
public:
    UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
	for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
    }
    UnionFind(int n):UnionFind(n,_DSU::mem[0],_DSU::mem[1]){}
    bool unite(int x, int y){
	x = find(x);y = find(y);
	if (x == y)return false;
	if (rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if (rank[x] == rank[y])rank[x]++;
	}
	return true;
    }
    bool same(int x, int y){
	return find(x) == find(y);
    }
};

#define fi first
#define se second
int N,Q;

T abc[212345];
queue<P> que[212345];
int main(){
    scanf("%d %d",&N,&Q);
    LL LB=1e15;
    REP(i,Q){
        int a,b;LL c;
        scanf("%d %d %lld",&b,&a,&c);
        abc[i]=T(a,b,c);
        chmin(LB,c);
    }
    
    REP(i,Q){
        int a,b;LL c;
        tie(a,b,c)=abc[i];
        c-=LB;
        if(c<2*N&&a!=b){
            que[c].push(P(a,b));
        }
        swap(a,b);
        a=(a+1)%N;
        c++;
        if(c<2*N&&a!=b){
            que[c].push(P(a,b));
        }
    }
    UnionFind uf(N);
    LL res=LB*(N-1);
    REP(i,2*N){
        while(!que[i].empty()){
            auto v=que[i].front();que[i].pop();
            int a,b;tie(a,b)=v;
            int c=i;
            if(!uf.same(a,b)){
                //cout<<a<<b<<c<<endl;
                res+=c;
                uf.unite(a,b);
                que[c+2].push(P((a+1)%N,(b+1)%N));
            }
        }
    }

    
    
    cout<<res<<endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&Q);
                         ^
./Main.cpp:62:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld",&b,&a,&c);
                                     ^

Judge Result