Submission #241799


Source Code Expand

Copy
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
struct edge {
  int src, dst, len;
  edge(int s, int d, int l)
    : src(s), dst(d), len(l) { }
};
typedef vector<edge> vertex;
typedef vector<vertex> graph;
bool operator < (const edge& e, const edge& f)
{
  return e.len > f.len;
}
#define MAX_N 100010
struct UF {
	int par[MAX_N],rank[MAX_N];
	
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = par[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(){
	int N, M;
	cin>>N>>M;
	N++;
	graph g(N);
	for(int i = 1; i < N; i++){
		int c;
		cin>>c;
		g[0].push_back(edge(0, i, c));
		g[i].push_back(edge(i, 0, c));
	}
	for(int i = 0; i < M; i++){
		int a, b, r;
		cin>>a>>b>>r;
		g[a].push_back(edge(a, b, r));
		g[b].push_back(edge(b, a ,r));
	}

	UF uf;
	uf.init(N);
	priority_queue<edge> q;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < g[i].size(); j++){
			edge e = g[i][j];
			if(i < e.dst) q.push(e);
		}
	}

	ll res = 0;
	while(!q.empty()){
		edge e = q.top(); q.pop();
		if(!uf.same(e.src, e.dst)){
			uf.unite(e.src, e.dst);
			res += e.len;
		}
	}
	cout<<res<<endl;
	return 0;
}

Submission Info

Submission Time
Task C - 高橋君と国家
User Lepton
Language C++ (G++ 4.6.4)
Score 100
Code Size 2039 Byte
Status
Exec Time 705 ms
Memory 21140 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 10 / 10 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 20 / 20 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 30 / 30 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Subtask4 40 / 40 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt, subtask4-01.txt, subtask4-02.txt, subtask4-03.txt, subtask4-04.txt, subtask4-05.txt, subtask4-06.txt, subtask4-07.txt, subtask4-08.txt, subtask4-09.txt, subtask4-10.txt, subtask4-11.txt, subtask4-12.txt, subtask4-13.txt, subtask4-14.txt, subtask4-15.txt, subtask4-16.txt, subtask4-17.txt, subtask4-18.txt, subtask4-19.txt, subtask4-20.txt, subtask4-21.txt, subtask4-22.txt, subtask4-23.txt, subtask4-24.txt, subtask4-25.txt, subtask4-26.txt, subtask4-27.txt, subtask4-28.txt, subtask4-29.txt, subtask4-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 23 ms 932 KB
subtask0-sample-02.txt 23 ms 788 KB
subtask0-sample-03.txt 23 ms 924 KB
subtask1-01.txt 23 ms 924 KB
subtask1-02.txt 24 ms 792 KB
subtask1-03.txt 22 ms 920 KB
subtask1-04.txt 23 ms 816 KB
subtask1-05.txt 23 ms 788 KB
subtask1-06.txt 23 ms 924 KB
subtask1-07.txt 23 ms 840 KB
subtask1-08.txt 24 ms 808 KB
subtask1-09.txt 24 ms 932 KB
subtask1-10.txt 22 ms 796 KB
subtask1-11.txt 21 ms 924 KB
subtask1-12.txt 23 ms 764 KB
subtask1-13.txt 22 ms 932 KB
subtask1-14.txt 24 ms 920 KB
subtask1-15.txt 22 ms 804 KB
subtask1-16.txt 23 ms 932 KB
subtask1-17.txt 22 ms 796 KB
subtask1-18.txt 21 ms 804 KB
subtask1-19.txt 23 ms 924 KB
subtask1-20.txt 24 ms 920 KB
subtask1-21.txt 24 ms 760 KB
subtask1-22.txt 23 ms 928 KB
subtask1-23.txt 23 ms 804 KB
subtask1-24.txt 22 ms 800 KB
subtask1-25.txt 23 ms 812 KB
subtask1-26.txt 24 ms 920 KB
subtask1-27.txt 24 ms 932 KB
subtask1-28.txt 24 ms 928 KB
subtask1-29.txt 24 ms 800 KB
subtask1-30.txt 24 ms 804 KB
subtask2-01.txt 23 ms 796 KB
subtask2-02.txt 22 ms 924 KB
subtask2-03.txt 27 ms 924 KB
subtask2-04.txt 25 ms 928 KB
subtask2-05.txt 22 ms 924 KB
subtask2-06.txt 26 ms 788 KB
subtask2-07.txt 42 ms 728 KB
subtask2-08.txt 21 ms 800 KB
subtask2-09.txt 23 ms 800 KB
subtask2-10.txt 23 ms 924 KB
subtask2-11.txt 25 ms 928 KB
subtask2-12.txt 23 ms 932 KB
subtask2-13.txt 23 ms 928 KB
subtask2-14.txt 25 ms 916 KB
subtask2-15.txt 29 ms 728 KB
subtask2-16.txt 24 ms 924 KB
subtask2-17.txt 23 ms 928 KB
subtask2-18.txt 24 ms 800 KB
subtask2-19.txt 22 ms 804 KB
subtask2-20.txt 24 ms 924 KB
subtask2-21.txt 23 ms 932 KB
subtask2-22.txt 25 ms 792 KB
subtask2-23.txt 23 ms 924 KB
subtask2-24.txt 23 ms 812 KB
subtask2-25.txt 24 ms 804 KB
subtask2-26.txt 24 ms 800 KB
subtask2-27.txt 24 ms 920 KB
subtask2-28.txt 23 ms 800 KB
subtask2-29.txt 23 ms 792 KB
subtask2-30.txt 23 ms 796 KB
subtask3-01.txt 24 ms 920 KB
subtask3-02.txt 23 ms 796 KB
subtask3-03.txt 24 ms 928 KB
subtask3-04.txt 26 ms 928 KB
subtask3-05.txt 30 ms 1056 KB
subtask3-06.txt 27 ms 992 KB
subtask3-07.txt 28 ms 936 KB
subtask3-08.txt 30 ms 1172 KB
subtask3-09.txt 33 ms 1192 KB
subtask3-10.txt 31 ms 1172 KB
subtask3-11.txt 32 ms 1184 KB
subtask3-12.txt 31 ms 1188 KB
subtask3-13.txt 32 ms 1188 KB
subtask3-14.txt 34 ms 1312 KB
subtask3-15.txt 36 ms 1308 KB
subtask3-16.txt 40 ms 1568 KB
subtask3-17.txt 37 ms 1432 KB
subtask3-18.txt 37 ms 1448 KB
subtask3-19.txt 36 ms 1444 KB
subtask3-20.txt 36 ms 1448 KB
subtask3-21.txt 38 ms 1456 KB
subtask3-22.txt 41 ms 1444 KB
subtask3-23.txt 37 ms 1440 KB
subtask3-24.txt 35 ms 1452 KB
subtask3-25.txt 37 ms 1524 KB
subtask3-26.txt 37 ms 1448 KB
subtask3-27.txt 36 ms 1452 KB
subtask3-28.txt 36 ms 1452 KB
subtask3-29.txt 38 ms 1448 KB
subtask3-30.txt 37 ms 1452 KB
subtask4-01.txt 43 ms 1760 KB
subtask4-02.txt 56 ms 2524 KB
subtask4-03.txt 70 ms 2912 KB
subtask4-04.txt 256 ms 8408 KB
subtask4-05.txt 357 ms 12888 KB
subtask4-06.txt 517 ms 16212 KB
subtask4-07.txt 522 ms 16212 KB
subtask4-08.txt 345 ms 13912 KB
subtask4-09.txt 455 ms 15320 KB
subtask4-10.txt 672 ms 21076 KB
subtask4-11.txt 705 ms 21072 KB
subtask4-12.txt 669 ms 21084 KB
subtask4-13.txt 659 ms 21084 KB
subtask4-14.txt 642 ms 21072 KB
subtask4-15.txt 658 ms 21080 KB
subtask4-16.txt 645 ms 21076 KB
subtask4-17.txt 652 ms 21068 KB
subtask4-18.txt 641 ms 21084 KB
subtask4-19.txt 653 ms 21076 KB
subtask4-20.txt 653 ms 21072 KB
subtask4-21.txt 666 ms 21072 KB
subtask4-22.txt 662 ms 21072 KB
subtask4-23.txt 657 ms 21084 KB
subtask4-24.txt 674 ms 21072 KB
subtask4-25.txt 659 ms 21080 KB
subtask4-26.txt 677 ms 21072 KB
subtask4-27.txt 664 ms 21080 KB
subtask4-28.txt 673 ms 21088 KB
subtask4-29.txt 674 ms 21080 KB
subtask4-30.txt 674 ms 21140 KB