Submission #242891


Source Code Expand

Copy
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>

#pragma warning( disable: 4996 )

using namespace std;

typedef long long ll;
typedef pair<int, int> P;


#define INF 1000000000
#define EPS 1e-10

#define MAX_N 100002
#define MAX_M 300002

int N, M;
int c[MAX_N];
int a[MAX_M];
int b[MAX_M];
int r[MAX_M];

int E = 0;

struct edge{
	int from;
	int to;
	int cost;
};

edge es[MAX_M];

//親都市をNにする
int par[MAX_N];
int 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] = x;
		if (Rank[x] == Rank[y])
			Rank[x]++;
	}

}

bool same(int x, int y){
	return find(x) == find(y);
}

bool comp(const edge& e1, const edge& e2){
	return e1.cost < e2.cost;
}

int solve(){
	int ans = 0;

	sort(es, es + E, comp);

	init(N);

	for (int i = 0; i < E; i++){
		edge e = es[i];
		if (!same(e.from, e.to)){
			unite(e.from, e.to);
			ans += e.cost;
		}
	}

	return ans;
}

int main() {

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		cin >> c[i];
		es[E] = {N, i, c[i]};
		E++;
	}

	for (int i = 0; i < M; i++){
		cin >> a[i] >> b[i] >> r[i];
		a[i]--;
		b[i]--;
		es[E] = { a[i], b[i], r[i] };
		E++;
	}

	cout << solve() << endl;

	return 0;
}

Submission Info

Submission Time
Task C - 高橋君と国家
User taketake0609
Language C++ (G++ 4.6.4)
Score 0
Code Size 1919 Byte
Status
Exec Time 564 ms
Memory 7900 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:122:22: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:122:22: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:130:30: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]
./Main.cpp:130:30: warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 0 / 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 0 / 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 0 / 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 0 / 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 53 ms 812 KB
subtask0-sample-02.txt 25 ms 872 KB
subtask0-sample-03.txt 26 ms 876 KB
subtask1-01.txt 25 ms 924 KB
subtask1-02.txt 26 ms 876 KB
subtask1-03.txt 26 ms 924 KB
subtask1-04.txt 27 ms 876 KB
subtask1-05.txt 27 ms 880 KB
subtask1-06.txt 27 ms 884 KB
subtask1-07.txt 27 ms 880 KB
subtask1-08.txt 27 ms 924 KB
subtask1-09.txt 27 ms 916 KB
subtask1-10.txt 27 ms 924 KB
subtask1-11.txt 27 ms 820 KB
subtask1-12.txt 28 ms 884 KB
subtask1-13.txt 26 ms 924 KB
subtask1-14.txt 27 ms 876 KB
subtask1-15.txt 27 ms 880 KB
subtask1-16.txt 27 ms 876 KB
subtask1-17.txt 27 ms 884 KB
subtask1-18.txt 27 ms 872 KB
subtask1-19.txt 54 ms 900 KB
subtask1-20.txt 44 ms 812 KB
subtask1-21.txt 48 ms 808 KB
subtask1-22.txt 26 ms 920 KB
subtask1-23.txt 30 ms 856 KB
subtask1-24.txt 28 ms 876 KB
subtask1-25.txt 27 ms 808 KB
subtask1-26.txt 30 ms 864 KB
subtask1-27.txt 27 ms 928 KB
subtask1-28.txt 27 ms 880 KB
subtask1-29.txt 26 ms 920 KB
subtask1-30.txt 27 ms 872 KB
subtask2-01.txt 28 ms 880 KB
subtask2-02.txt 27 ms 880 KB
subtask2-03.txt 27 ms 876 KB
subtask2-04.txt 26 ms 880 KB
subtask2-05.txt 25 ms 920 KB
subtask2-06.txt 26 ms 924 KB
subtask2-07.txt 26 ms 872 KB
subtask2-08.txt 26 ms 872 KB
subtask2-09.txt 26 ms 924 KB
subtask2-10.txt 27 ms 812 KB
subtask2-11.txt 26 ms 872 KB
subtask2-12.txt 26 ms 920 KB
subtask2-13.txt 26 ms 872 KB
subtask2-14.txt 28 ms 812 KB
subtask2-15.txt 27 ms 876 KB
subtask2-16.txt 26 ms 920 KB
subtask2-17.txt 26 ms 884 KB
subtask2-18.txt 26 ms 920 KB
subtask2-19.txt 26 ms 928 KB
subtask2-20.txt 26 ms 876 KB
subtask2-21.txt 26 ms 928 KB
subtask2-22.txt 26 ms 880 KB
subtask2-23.txt 27 ms 884 KB
subtask2-24.txt 26 ms 816 KB
subtask2-25.txt 26 ms 856 KB
subtask2-26.txt 26 ms 876 KB
subtask2-27.txt 26 ms 816 KB
subtask2-28.txt 26 ms 884 KB
subtask2-29.txt 26 ms 880 KB
subtask2-30.txt 26 ms 876 KB
subtask3-01.txt 28 ms 920 KB
subtask3-02.txt 27 ms 876 KB
subtask3-03.txt 29 ms 876 KB
subtask3-04.txt 29 ms 928 KB
subtask3-05.txt 32 ms 880 KB
subtask3-06.txt 30 ms 876 KB
subtask3-07.txt 30 ms 928 KB
subtask3-08.txt 33 ms 1000 KB
subtask3-09.txt 32 ms 1000 KB
subtask3-10.txt 33 ms 1052 KB
subtask3-11.txt 32 ms 1016 KB
subtask3-12.txt 32 ms 924 KB
subtask3-13.txt 34 ms 1012 KB
subtask3-14.txt 40 ms 1044 KB
subtask3-15.txt 36 ms 1008 KB
subtask3-16.txt 39 ms 1004 KB
subtask3-17.txt 40 ms 1000 KB
subtask3-18.txt 39 ms 1004 KB
subtask3-19.txt 39 ms 1008 KB
subtask3-20.txt 38 ms 1000 KB
subtask3-21.txt 37 ms 1008 KB
subtask3-22.txt 39 ms 1004 KB
subtask3-23.txt 39 ms 1012 KB
subtask3-24.txt 38 ms 1004 KB
subtask3-25.txt 39 ms 1004 KB
subtask3-26.txt 39 ms 1008 KB
subtask3-27.txt 39 ms 1008 KB
subtask3-28.txt 39 ms 1004 KB
subtask3-29.txt 39 ms 1004 KB
subtask3-30.txt 39 ms 1004 KB
subtask4-01.txt 46 ms 1136 KB
subtask4-02.txt 57 ms 1388 KB
subtask4-03.txt 68 ms 1516 KB
subtask4-04.txt 223 ms 3832 KB
subtask4-05.txt 309 ms 4980 KB
subtask4-06.txt 440 ms 6636 KB
subtask4-07.txt 448 ms 6692 KB
subtask4-08.txt 281 ms 5104 KB
subtask4-09.txt 368 ms 6028 KB
subtask4-10.txt 524 ms 7788 KB
subtask4-11.txt 555 ms 7852 KB
subtask4-12.txt 535 ms 7852 KB
subtask4-13.txt 533 ms 7848 KB
subtask4-14.txt 523 ms 7900 KB
subtask4-15.txt 532 ms 7848 KB
subtask4-16.txt 526 ms 7780 KB
subtask4-17.txt 529 ms 7784 KB
subtask4-18.txt 529 ms 7788 KB
subtask4-19.txt 532 ms 7856 KB
subtask4-20.txt 564 ms 7848 KB
subtask4-21.txt 533 ms 7856 KB
subtask4-22.txt 535 ms 7852 KB
subtask4-23.txt 530 ms 7856 KB
subtask4-24.txt 531 ms 7844 KB
subtask4-25.txt 529 ms 7856 KB
subtask4-26.txt 523 ms 7900 KB
subtask4-27.txt 526 ms 7780 KB
subtask4-28.txt 530 ms 7848 KB
subtask4-29.txt 526 ms 7860 KB
subtask4-30.txt 540 ms 7792 KB