Submission #10066140


Source Code Expand

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
struct unionfind{
    vector<int> par, sz;
    unionfind() {}
    unionfind(int n):par(n), sz(n, 1){
        for(int i=0; i<n; i++) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return 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);
        par[x]=y;
        sz[y]+=sz[x];
    }
    bool same(int x, int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};
int main()
{
    int n, q;
	cin>>n>>q;
	int a[200020], b[200020];
	ll c[200020];
	using edge=pair<ll, P>;
	vector<edge> v;
	ll mn[200020];
	const ll INF=1e18;
	fill(mn, mn+n, INF);
	ll d=INF;
	for(int i=0; i<q; i++){
		cin>>a[i]>>b[i]>>c[i];
		d=min(d, c[i]+1+2*(n-a[i]));
		mn[a[i]]=min(mn[a[i]], c[i]+1);
		d=min(d, c[i]+2+2*(n-b[i]));
		mn[b[i]]=min(mn[b[i]], c[i]+2);
		v.push_back({c[i], {a[i], b[i]}});
	}
	for(int i=0; i<n; i++){
		d=min(d, mn[i]);
		v.push_back({d, {i, (i+1)%n}});
		d+=2;
	}
	sort(v.begin(), v.end());
	unionfind uf(n);
	ll ans=0;
	for(auto e:v){
		int x=e.second.first, y=e.second.second;
		if(!uf.same(x, y)){
			uf.unite(x, y);
			ans+=e.first;
		}
	}
	cout<<ans<<endl;
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User chocorusk
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1880 Byte
Status AC
Exec Time 267 ms
Memory 15084 KB

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 2 ms 4352 KB
01-02.txt AC 163 ms 9328 KB
01-03.txt AC 267 ms 13676 KB
01-04.txt AC 24 ms 9584 KB
01-05.txt AC 16 ms 8944 KB
01-06.txt AC 21 ms 9840 KB
01-07.txt AC 20 ms 9840 KB
01-08.txt AC 22 ms 9968 KB
01-09.txt AC 33 ms 8428 KB
01-10.txt AC 132 ms 13292 KB
01-11.txt AC 225 ms 12780 KB
01-12.txt AC 243 ms 14316 KB
01-13.txt AC 243 ms 13676 KB
01-14.txt AC 249 ms 14956 KB
01-15.txt AC 245 ms 13548 KB
01-16.txt AC 240 ms 13292 KB
01-17.txt AC 241 ms 13292 KB
01-18.txt AC 221 ms 15084 KB
01-19.txt AC 19 ms 9968 KB
01-20.txt AC 28 ms 9712 KB
01-21.txt AC 77 ms 10348 KB
01-22.txt AC 197 ms 13804 KB
01-23.txt AC 199 ms 14316 KB
01-24.txt AC 27 ms 8812 KB
01-25.txt AC 241 ms 15084 KB
01-26.txt AC 25 ms 7664 KB
01-27.txt AC 36 ms 8172 KB
01-28.txt AC 159 ms 13164 KB
01-29.txt AC 228 ms 14188 KB
01-30.txt AC 244 ms 14700 KB
sample-01.txt AC 2 ms 2304 KB
sample-02.txt AC 2 ms 2304 KB
sample-03.txt AC 2 ms 2304 KB