(cache)Submission #67050782 - AtCoder Beginner Contest 409

Contest Duration: 2025-06-07(Sat) 21:00 - 2025-06-07(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #67050782

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int N;
int x[114514];
struct edge_s {
  int to, cost;
};
int ec[114514];
struct edge_s* es[114514];
void ae(int f, int t, int c) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = (struct edge_s){ t, c };
}
uint64_t ans = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int N;
int x[114514];

struct edge_s {
	int to, cost;
};

int ec[114514];
struct edge_s* es[114514];

void ae(int f, int t, int c) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = (struct edge_s){ t, c };
}

uint64_t ans = 0;

int dfs(int node, int parent) {
	int sum = x[node];
	int i;
	for (i = 0; i < ec[node]; i++) {
		if (es[node][i].to != parent) {
			int cnt = dfs(es[node][i].to, node);
			sum += cnt;
			ans += (uint64_t)es[node][i].cost * abs(cnt);
		}
	}
	return sum;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &x[i]) != 1) return 1;
	}
	for (i = 1; i < N; i++) {
		int u, v, w;
		if (scanf("%d%d%d", &u, &v, &w) != 3) return 1;
		ae(u, v, w);
		ae(v, u, w);
	}
	dfs(1, 0);
	printf("%" PRIu64 "\n", ans);
	return 0;
}

/*

「迎えに行く」と「持ってくる」でコストは変わらない (予想)
よって、適当な根を決めてそこに集めればいい (予想)

*/

Submission Info

Submission Time	2025-06-25 03:57:37
Task	E - Pair Annihilation
User	mikecat
Language	C (gcc 12.2.0)
Score	425
Code Size	1139 Byte
Status	AC
Exec Time	40 ms
Memory	11076 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 3

× 27

Set Name	Test Cases
Sample	00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All	00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt

Case Name	Status	Exec Time	Memory
00_sample_01.txt	AC	0 ms	1628 KiB
00_sample_02.txt	AC	0 ms	1628 KiB
00_sample_03.txt	AC	0 ms	1632 KiB
01_test_01.txt	AC	11 ms	2964 KiB
01_test_02.txt	AC	39 ms	6540 KiB
01_test_03.txt	AC	5 ms	2332 KiB
01_test_04.txt	AC	38 ms	6572 KiB
01_test_05.txt	AC	35 ms	6208 KiB
01_test_06.txt	AC	39 ms	6524 KiB
01_test_07.txt	AC	24 ms	4724 KiB
01_test_08.txt	AC	38 ms	6660 KiB
01_test_09.txt	AC	35 ms	6096 KiB
01_test_10.txt	AC	39 ms	6656 KiB
01_test_11.txt	AC	38 ms	6548 KiB
01_test_12.txt	AC	39 ms	6664 KiB
01_test_13.txt	AC	16 ms	3640 KiB
01_test_14.txt	AC	39 ms	6660 KiB
01_test_15.txt	AC	18 ms	3976 KiB
01_test_16.txt	AC	40 ms	6588 KiB
01_test_17.txt	AC	11 ms	3200 KiB
01_test_18.txt	AC	38 ms	6540 KiB
01_test_19.txt	AC	26 ms	4992 KiB
01_test_20.txt	AC	39 ms	6516 KiB
01_test_21.txt	AC	26 ms	11076 KiB
01_test_22.txt	AC	26 ms	10992 KiB
01_test_23.txt	AC	27 ms	7116 KiB
01_test_24.txt	AC	24 ms	7140 KiB