Submission #1869952
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int N = 1e5 + 5, M = N << 1, inf = 1e9 + 7 ;
using namespace std ;
int n, e, ter[M], nxt[M], lnk[N], w[M], sz[N], fa[N] ;
ll ans ;
void add(int x, int y, int z) {
ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e, w[e] = z ;
}
void dfs(int p, int las) {
sz[p] = 1, fa[p] = las ;
for (int i = lnk[p] ; i; i = nxt[i]) if (ter[i] != las) {
dfs(ter[i], p) ;
sz[p] += sz[ter[i]] ;
ans += 2LL * w[i] * min(sz[ter[i]], n - sz[ter[i]]) ;
}
}
int main() {
scanf("%d", &n) ;
int x, y, z ;
rep(i, 1, n - 1) {
scanf("%d%d%d", &x, &y, &z) ;
add(x, y, z), add(y, x, z) ;
}
ans = 0 ;
dfs(1, 0) ;
rep(i, 1, n) for (int j = lnk[i] ; j; j = nxt[j]) if (ter[j] != fa[i]) {
if (sz[ter[j]] == n / 2 && n - sz[ter[j]] == n / 2) {
printf("%lld\n", ans - w[j]) ;
return 0 ;
}
}
rep(i, 1, n) {
bool flg = true ; int mn = inf ;
for (int j = lnk[i] ; j; j = nxt[j]) {
if (ter[j] == fa[i]) flg &= (n - sz[i] <= n / 2) ;
else flg &= (sz[ter[j]] <= n / 2) ;
mn = min(mn, w[j]) ;
}
if (flg) {
printf("%lld\n", ans - mn) ;
return 0 ;
}
}
return 0 ;
}
Submission Info
Submission Time |
|
Task |
D - Tree and Hamilton Path |
User |
mjy0724 |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
1311 Byte |
Status |
AC |
Exec Time |
39 ms |
Memory |
7808 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:28:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n) ;
^
./Main.cpp:31:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &z) ;
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
32 ms |
3456 KB |
subtask_1_03.txt |
AC |
17 ms |
1920 KB |
subtask_1_04.txt |
AC |
34 ms |
3712 KB |
subtask_1_05.txt |
AC |
19 ms |
2944 KB |
subtask_1_06.txt |
AC |
15 ms |
1792 KB |
subtask_1_07.txt |
AC |
15 ms |
1792 KB |
subtask_1_08.txt |
AC |
17 ms |
2048 KB |
subtask_1_09.txt |
AC |
11 ms |
1408 KB |
subtask_1_10.txt |
AC |
5 ms |
1152 KB |
subtask_1_11.txt |
AC |
10 ms |
1280 KB |
subtask_1_12.txt |
AC |
37 ms |
3712 KB |
subtask_1_13.txt |
AC |
34 ms |
3712 KB |
subtask_1_14.txt |
AC |
35 ms |
3712 KB |
subtask_1_15.txt |
AC |
35 ms |
3712 KB |
subtask_1_16.txt |
AC |
35 ms |
3712 KB |
subtask_1_17.txt |
AC |
35 ms |
3712 KB |
subtask_1_18.txt |
AC |
36 ms |
3712 KB |
subtask_1_19.txt |
AC |
34 ms |
3712 KB |
subtask_1_20.txt |
AC |
35 ms |
3712 KB |
subtask_1_21.txt |
AC |
35 ms |
3712 KB |
subtask_1_22.txt |
AC |
34 ms |
3840 KB |
subtask_1_23.txt |
AC |
37 ms |
6400 KB |
subtask_1_24.txt |
AC |
37 ms |
7552 KB |
subtask_1_25.txt |
AC |
37 ms |
3840 KB |
subtask_1_26.txt |
AC |
39 ms |
4864 KB |
subtask_1_27.txt |
AC |
37 ms |
7168 KB |
subtask_1_28.txt |
AC |
35 ms |
3840 KB |
subtask_1_29.txt |
AC |
37 ms |
7808 KB |
subtask_1_30.txt |
AC |
37 ms |
6784 KB |
subtask_1_31.txt |
AC |
34 ms |
3712 KB |
subtask_1_32.txt |
AC |
32 ms |
3712 KB |
subtask_1_33.txt |
AC |
22 ms |
2816 KB |
subtask_1_34.txt |
AC |
29 ms |
3712 KB |