Submission #1112257


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,int> T;
typedef pair<int,int> P;


namespace _DSU{
#define SZ 212345
    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];
vector<P> que[412345];
int main(){
    scanf("%d %d",&N,&Q);
    int LB=1e9;
    REP(i,Q){
        int a,b, c;
        scanf("%d %d %d",&a,&b,&c);
        abc[i]=T(a,b,c);
        chmin(LB,c);
    }
    
    REP(i,Q){
        int a,b,c;
        tie(a,b,c)=abc[i];
        c-=LB;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
        a=(a+1)%N;
        c++;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
    }
    UnionFind uf(N);
    LL res=LB*(LL)(N-1);
    
    REP(i,2*N){
        while(!que[i].empty()){
            auto v=que[i].back();que[i].pop_back();
            int a,b;
            tie(a,b)=v;
            int c=i;
            //cout<<a<<b<<c<<endl;
            if(!uf.same(a,b)){
                res+=c;
                uf.unite(a,b);
                que[c+2].push_back(P((a+1)%N,(b+1)%N));
            }
        }
    }
    
    
    
    
    cout<<res<<endl;

    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User btk15049
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 2110 Byte
Status AC
Exec Time 130 ms
Memory 24832 KB

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:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
                                   ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 36
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 5 ms 12544 KB
01-02.txt AC 51 ms 12544 KB
01-03.txt AC 70 ms 17280 KB
01-04.txt AC 19 ms 20224 KB
01-05.txt AC 19 ms 19968 KB
01-06.txt AC 19 ms 19072 KB
01-07.txt AC 17 ms 16896 KB
01-08.txt AC 15 ms 16640 KB
01-09.txt AC 18 ms 16896 KB
01-10.txt AC 66 ms 21248 KB
01-11.txt AC 102 ms 21376 KB
01-12.txt AC 120 ms 24704 KB
01-13.txt AC 122 ms 24704 KB
01-14.txt AC 121 ms 24704 KB
01-15.txt AC 120 ms 24832 KB
01-16.txt AC 128 ms 24704 KB
01-17.txt AC 130 ms 24704 KB
01-18.txt AC 73 ms 21744 KB
01-19.txt AC 17 ms 17664 KB
01-20.txt AC 14 ms 16000 KB
01-21.txt AC 31 ms 16500 KB
01-22.txt AC 70 ms 20196 KB
01-23.txt AC 71 ms 20196 KB
01-24.txt AC 23 ms 20224 KB
01-25.txt AC 78 ms 20224 KB
01-26.txt AC 17 ms 17024 KB
01-27.txt AC 21 ms 18176 KB
01-28.txt AC 55 ms 19928 KB
01-29.txt AC 71 ms 18756 KB
01-30.txt AC 78 ms 21188 KB
sample-01.txt AC 5 ms 12544 KB
sample-02.txt AC 5 ms 12544 KB
sample-03.txt AC 5 ms 12544 KB