CODE FESTIVAL 2016 Final

Submission #10066140

Source codeソースコード

#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

Task問題 G - Zigzag MST
User nameユーザ名 chocorusk
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1300
Source lengthソースコード長 1880 Byte
File nameファイル名
Exec time実行時間 267 ms
Memory usageメモリ使用量 15084 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1300 / 1300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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