(cache)Submission #68665117 - AtCoder Beginner Contest 416

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

Submission #68665117

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 <inttypes.h>
#define INF INT64_C(1010101010101010101)
int N, M;
int A[114514], B[114514], C[114514];
int K, T;
int D[512];
int Q;
int Query[1024][4];
int64_t dists[512][512];
int64_t dist_sum = 0;
void dist_chmin(int i, int j, int64_t value) {
  if (dists[i][j] > value) {
    if (i > 0 && j > 0 && dists[i][j] < INF) dist_sum -= dists[i][j];
    dists[i][j] = value;
    if (i > 0 && j > 0 && dists[i][j] < INF) dist_sum += dists[i][j];
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define INF INT64_C(1010101010101010101)

int N, M;
int A[114514], B[114514], C[114514];
int K, T;
int D[512];
int Q;
int Query[1024][4];

int64_t dists[512][512];
int64_t dist_sum = 0;

void dist_chmin(int i, int j, int64_t value) {
	if (dists[i][j] > value) {
		if (i > 0 && j > 0 && dists[i][j] < INF) dist_sum -= dists[i][j];
		dists[i][j] = value;
		if (i > 0 && j > 0 && dists[i][j] < INF) dist_sum += dists[i][j];
	}
}

void kousinn(int target) {
	int i, j;
	for (i = 0; i <= N; i++) {
		for (j = 0; j <= N; j++) {
			dist_chmin(i, j, dists[i][target] + dists[target][j]);
		}
	}
}

int main(void) {
	int i, j, k;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d%d%d", &A[i], &B[i], &C[i]) != 3) return 1;
	}
	if (scanf("%d%d", &K, &T) != 2) return 1;
	for (i = 0; i < K; i++) {
		if (scanf("%d", &D[i]) != 1) return 1;
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d", &Query[i][0]) != 1) return 1;
		if (Query[i][0] == 1) {
			if (scanf("%d%d%d", &Query[i][1], &Query[i][2], &Query[i][3]) != 3) return 1;
		} else if (Query[i][0] == 2) {
			if (scanf("%d", &Query[i][1]) != 1) return 1;
		}
	}

	for (i = 0; i <= N; i++) {
		for (j = 0; j <= N; j++) {
			dists[i][j] = i == j ? 0 : INF;
		}
	}
	for (i = 0; i < M; i++) {
		if (C[i] < dists[A[i]][B[i]]) dists[A[i]][B[i]] = C[i];
		if (C[i] < dists[B[i]][A[i]]) dists[B[i]][A[i]] = C[i];
	}
	for (i = 0; i < K; i++) {
		dists[D[i]][0] = T;
		dists[0][D[i]] = 0;
	}
	for (k = 0; k <= N; k++) {
		for (i = 0; i <= N; i++) {
			for (j = 0; j <= N; j++) {
				if (dists[i][j] > dists[i][k] + dists[k][j]) {
					dists[i][j] = dists[i][k] + dists[k][j];
				}
			}
		}
	}
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			if (dists[i][j] < INF) dist_sum += dists[i][j];
		}
	}

	for (i = 0; i < Q; i++) {
		if (Query[i][0] == 1) {
			dist_chmin(Query[i][1], Query[i][2], Query[i][3]);
			dist_chmin(Query[i][2], Query[i][1], Query[i][3]);
			kousinn(Query[i][1]);
			kousinn(Query[i][2]);
		} else if (Query[i][0] == 2) {
			dist_chmin(Query[i][1], 0, T);
			dist_chmin(0, Query[i][1], 0);
			kousinn(Query[i][1]);
			kousinn(0);
		} else if (Query[i][0] == 3) {
			printf("%" PRId64 "\n", dist_sum);
		}
	}

	return 0;
}

Submission Info

Submission Time	2025-08-21 06:58:47
Task	E - Development
User	mikecat
Language	C (gcc 12.2.0)
Score	450
Code Size	2397 Byte
Status	AC
Exec Time	276 ms
Memory	4404 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 1

× 29

Set Name	Test Cases
Sample	sample_01.txt
All	hand.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, sample_01.txt

Case Name	Status	Exec Time	Memory
hand.txt	AC	0 ms	1756 KiB
random_01.txt	AC	260 ms	3672 KiB
random_02.txt	AC	58 ms	2660 KiB
random_03.txt	AC	257 ms	3752 KiB
random_04.txt	AC	200 ms	3556 KiB
random_05.txt	AC	260 ms	3780 KiB
random_06.txt	AC	74 ms	2880 KiB
random_07.txt	AC	261 ms	3624 KiB
random_08.txt	AC	243 ms	3704 KiB
random_09.txt	AC	265 ms	3640 KiB
random_10.txt	AC	78 ms	2820 KiB
random_11.txt	AC	267 ms	3640 KiB
random_12.txt	AC	138 ms	3176 KiB
random_13.txt	AC	262 ms	3696 KiB
random_14.txt	AC	65 ms	2724 KiB
random_15.txt	AC	264 ms	3760 KiB
random_16.txt	AC	163 ms	3256 KiB
random_17.txt	AC	267 ms	3648 KiB
random_18.txt	AC	201 ms	3380 KiB
random_19.txt	AC	264 ms	3680 KiB
random_20.txt	AC	196 ms	3388 KiB
random_21.txt	AC	54 ms	4060 KiB
random_22.txt	AC	104 ms	3028 KiB
random_23.txt	AC	167 ms	4404 KiB
random_24.txt	AC	111 ms	3080 KiB
random_25.txt	AC	243 ms	3772 KiB
random_26.txt	AC	241 ms	3688 KiB
random_27.txt	AC	276 ms	3672 KiB
sample_01.txt	AC	0 ms	1624 KiB