Submission #1357018
Source Code Expand
#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]]));
}
}
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 Info
Submission Time
2017-06-16 21:57:40+0900
Task
A - Graph
User
square1001
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1140 Byte
Status
WA
Exec Time
189 ms
Memory
69888 KB
Compile Error
./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:29:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
^
./Main.cpp:31: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--;
^
Judge Result
Set Name
Sample
subtask1
subtask2
All
Score / Max Score
0 / 0
0 / 200
0 / 300
0 / 200
Status
Set Name
Test Cases
Sample
sample_1.txt, sample_2.txt
subtask1
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
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
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
Case Name
Status
Exec Time
Memory
sample_1.txt
AC
2 ms
6528 KB
sample_2.txt
WA
2 ms
6528 KB
subtask_1_1.txt
WA
3 ms
6912 KB
subtask_1_10.txt
WA
84 ms
67840 KB
subtask_1_11.txt
AC
2 ms
6528 KB
subtask_1_2.txt
WA
28 ms
67200 KB
subtask_1_3.txt
WA
155 ms
68480 KB
subtask_1_4.txt
WA
17 ms
67840 KB
subtask_1_5.txt
WA
17 ms
67328 KB
subtask_1_6.txt
WA
49 ms
67328 KB
subtask_1_7.txt
WA
155 ms
68608 KB
subtask_1_8.txt
WA
17 ms
67712 KB
subtask_1_9.txt
WA
18 ms
67200 KB
subtask_2_1.txt
WA
156 ms
68608 KB
subtask_2_2.txt
WA
156 ms
68608 KB
subtask_2_3.txt
WA
156 ms
68608 KB
subtask_2_4.txt
WA
156 ms
68608 KB
subtask_2_5.txt
WA
18 ms
67840 KB
subtask_2_6.txt
WA
23 ms
67072 KB
subtask_2_7.txt
WA
50 ms
67456 KB
subtask_2_8.txt
WA
156 ms
68608 KB
subtask_3_1.txt
WA
189 ms
69888 KB
subtask_3_2.txt
WA
189 ms
69760 KB
subtask_3_3.txt
WA
51 ms
69120 KB
subtask_3_4.txt
WA
52 ms
68480 KB
subtask_3_5.txt
WA
118 ms
68992 KB
subtask_3_6.txt
WA
153 ms
69376 KB
subtask_3_7.txt
WA
189 ms
69888 KB
subtask_3_8.txt
WA
189 ms
69760 KB