Submission #1112246


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];
queue<int> 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(a<<16+b);
        }
        a=(a+1)%N;
        c++;
        if(c<2*N&&a!=b){
            que[c].push(a<<16+b);
        }
    }
    UnionFind uf(N);
    LL res=LB*(LL)(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)){
                res+=c;
                uf.unite(a,b);
                que[c+2].push(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 0
Code Size 2048 Byte
Status MLE
Exec Time 289 ms
Memory 283008 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 0 / 1300
Status
MLE × 3
MLE × 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 MLE 205 ms 279936 KB
01-02.txt MLE 250 ms 279936 KB
01-03.txt MLE 258 ms 281344 KB
01-04.txt MLE 205 ms 281344 KB
01-05.txt MLE 205 ms 281344 KB
01-06.txt MLE 205 ms 281344 KB
01-07.txt MLE 205 ms 281344 KB
01-08.txt MLE 205 ms 281344 KB
01-09.txt MLE 209 ms 281344 KB
01-10.txt MLE 247 ms 281344 KB
01-11.txt MLE 278 ms 280576 KB
01-12.txt MLE 287 ms 281344 KB
01-13.txt MLE 287 ms 281344 KB
01-14.txt MLE 289 ms 281344 KB
01-15.txt MLE 287 ms 281344 KB
01-16.txt MLE 287 ms 281344 KB
01-17.txt MLE 287 ms 281344 KB
01-18.txt MLE 279 ms 282112 KB
01-19.txt MLE 205 ms 281344 KB
01-20.txt MLE 227 ms 281344 KB
01-21.txt MLE 240 ms 281856 KB
01-22.txt MLE 273 ms 283008 KB
01-23.txt MLE 274 ms 283008 KB
01-24.txt MLE 210 ms 281344 KB
01-25.txt MLE 273 ms 281344 KB
01-26.txt MLE 205 ms 281344 KB
01-27.txt MLE 230 ms 281472 KB
01-28.txt MLE 260 ms 282368 KB
01-29.txt MLE 280 ms 282368 KB
01-30.txt MLE 282 ms 283008 KB
sample-01.txt MLE 205 ms 279936 KB
sample-02.txt MLE 204 ms 279936 KB
sample-03.txt MLE 207 ms 279936 KB