CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel)

Submission #1357021

Source codeソースコード

#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
int N, M, Q, s, t, a[400009], b[400009], c[400009], p[400009], par[4009], d[4009][4009]; vector<pair<int, int> > g[4009];
int root(int x) { return x == par[x] ? x : par[x] = root(par[x]); }
void dfs(int pos, int pre, int st, int val) {
	d[st][pos] = val;
	for (pair<int, int> i : g[pos]) {
		if (i.first == pre) continue;
		dfs(i.first, pos, st, max(val, i.second));
	}
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) scanf("%d %d %d", &a[i], &b[i], &c[i]), a[i]--, b[i]--, p[i] = i;
	sort(p, p + M, [](int i, int j) { return c[i] < c[j]; });
	for (int i = 0; i < N; i++) par[i] = i;
	long long sum = 0;
	for (int i = 0; i < M; i++) {
		int pa = root(a[p[i]]), pb = root(b[p[i]]);
		if (pa != pb) {
			par[pa] = pb; sum += c[p[i]];
			g[a[p[i]]].push_back(make_pair(b[p[i]], c[p[i]]));
			g[b[p[i]]].push_back(make_pair(a[p[i]], c[p[i]]));
		}
	}
	for (int i = 0; i < N; i++) dfs(i, -1, i, 0);
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++) {
		scanf("%d %d", &s, &t); s--, t--;
		printf("%lld\n", sum - d[s][t]);
	}
	return 0;
}

Submission

Task問題 A - グラフ / Graph
User nameユーザ名 square1001
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1195 Byte
File nameファイル名
Exec time実行時間 510 ms
Memory usageメモリ使用量 70656 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:16:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
^
./Main.cpp:17:94: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < M; i++) scanf("%d %d %d", &a[i], &b[i], &c[i]), a[i]--, b[i]--, p[i] = i;
^
./Main.cpp:30:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
^
./Main.cpp:32:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &s, &t); s--, t--;
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt
subtask1 200 / 200 sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 300 / 300 sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt
All 200 / 200 sample_1.txt,sample_2.txt,sample_1.txt,sample_2.txt,subtask_1_1.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 2 ms 6528 KB
sample_2.txt AC 2 ms 6528 KB
subtask_1_1.txt AC 3 ms 6912 KB
subtask_1_10.txt AC 396 ms 68736 KB
subtask_1_11.txt AC 2 ms 6528 KB
subtask_1_2.txt AC 370 ms 68096 KB
subtask_1_3.txt AC 472 ms 69504 KB
subtask_1_4.txt AC 308 ms 67968 KB
subtask_1_5.txt AC 341 ms 67968 KB
subtask_1_6.txt AC 362 ms 68352 KB
subtask_1_7.txt AC 473 ms 69504 KB
subtask_1_8.txt AC 313 ms 67968 KB
subtask_1_9.txt AC 365 ms 67968 KB
subtask_2_1.txt AC 478 ms 69632 KB
subtask_2_2.txt AC 482 ms 69504 KB
subtask_2_3.txt AC 473 ms 69504 KB
subtask_2_4.txt AC 475 ms 69504 KB
subtask_2_5.txt AC 306 ms 67968 KB
subtask_2_6.txt AC 356 ms 68096 KB
subtask_2_7.txt AC 380 ms 68352 KB
subtask_2_8.txt AC 470 ms 69504 KB
subtask_3_1.txt AC 499 ms 70656 KB
subtask_3_2.txt AC 509 ms 70656 KB
subtask_3_3.txt AC 342 ms 69376 KB
subtask_3_4.txt AC 391 ms 69248 KB
subtask_3_5.txt AC 444 ms 69888 KB
subtask_3_6.txt AC 466 ms 70272 KB
subtask_3_7.txt AC 510 ms 70656 KB
subtask_3_8.txt AC 508 ms 70656 KB