(cache)Submission #69989732 - 灘校文化祭コンテスト 2022 Day1

Contest Duration: 2022-05-03(Tue) 13:00 - 2022-05-03(Tue) 16:00 (local time) (180 minutes) Back to Home

Submission #69989732

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 <string.h>
int H, W, K;
char A[2048][2048];
long long maguma_time[2048][2048];
int player_time[2048][2048];
struct yx_s {
  int y, x;
} q[2048 * 2048];
int main(void) {
  int i, j;
  int qs = 0, qe = 0;
  if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
  memset(maguma_time, 0x7f, sizeof(maguma_time));
  memset(player_time, 0x7f, sizeof(player_time));
  for (i = 1; i <= H; i++) {
    if (scanf("%2046s", A[i] + 1) != 1) return 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <string.h>

int H, W, K;
char A[2048][2048];

long long maguma_time[2048][2048];
int player_time[2048][2048];

struct yx_s {
	int y, x;
} q[2048 * 2048];

int main(void) {
	int i, j;
	int qs = 0, qe = 0;
	if (scanf("%d%d%d", &H, &W, &K) != 3) return 1;
	memset(maguma_time, 0x7f, sizeof(maguma_time));
	memset(player_time, 0x7f, sizeof(player_time));
	for (i = 1; i <= H; i++) {
		if (scanf("%2046s", A[i] + 1) != 1) return 1;
		for (j = 1; j <= W; j++) {
			if (A[i][j] == '@') {
				maguma_time[i][j] = 0;
				q[qe++] = (struct yx_s){ i, j };
			}
		}
	}
	while (qs < qe) {
		struct yx_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int ny = cur.y + (i < 2) * ((i & 1) * 2 - 1);
			int nx = cur.x + (i >= 2) * ((i & 1) * 2 - 1);
			if (A[ny][nx] == '.' && maguma_time[ny][nx] > maguma_time[cur.y][cur.x] + K) {
				maguma_time[ny][nx] = maguma_time[cur.y][cur.x] + K;
				q[qe++] = (struct yx_s){ ny, nx };
			}
		}
	}
	qs = 0;
	qe = 1;
	q[0] = (struct yx_s){ 1, 1 };
	player_time[1][1] = 0;
	while (qs < qe) {
		struct yx_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int ny = cur.y + (i < 2) * ((i & 1) * 2 - 1);
			int nx = cur.x + (i >= 2) * ((i & 1) * 2 - 1);
			if (
				A[ny][nx] == '.' &&
				player_time[ny][nx] > player_time[cur.y][cur.x] + 1 &&
				player_time[cur.y][cur.x] + 1 < maguma_time[ny][nx]
			) {
				player_time[ny][nx] = player_time[cur.y][cur.x] + 1;
				q[qe++] = (struct yx_s){ ny, nx };
				if (ny == H && nx == W) {
					puts("Yes");
					return 0;
				}
			}
		}
	}
	puts("No");
	return 0;
}

Submission Info

Submission Time	2025-10-10 00:36:49
Task	C - Flood
User	mikecat
Language	C (gcc 12.2.0)
Score	400
Code Size	1620 Byte
Status	AC
Exec Time	253 ms
Memory	81328 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 4

× 54

Set Name	Test Cases
Sample	example_00.txt, example_01.txt, example_02.txt, example_03.txt
All	example_00.txt, example_01.txt, example_02.txt, example_03.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	21 ms	50784 KiB
example_01.txt	AC	21 ms	50728 KiB
example_02.txt	AC	21 ms	50788 KiB
example_03.txt	AC	20 ms	50784 KiB
test_00.txt	AC	33 ms	54200 KiB
test_01.txt	AC	94 ms	64500 KiB
test_02.txt	AC	23 ms	51428 KiB
test_03.txt	AC	65 ms	59252 KiB
test_04.txt	AC	129 ms	65484 KiB
test_05.txt	AC	25 ms	53280 KiB
test_06.txt	AC	36 ms	53752 KiB
test_07.txt	AC	38 ms	55952 KiB
test_08.txt	AC	43 ms	54288 KiB
test_09.txt	AC	24 ms	51328 KiB
test_10.txt	AC	21 ms	50776 KiB
test_11.txt	AC	55 ms	58960 KiB
test_12.txt	AC	24 ms	51696 KiB
test_13.txt	AC	27 ms	51916 KiB
test_14.txt	AC	132 ms	67804 KiB
test_15.txt	AC	43 ms	54988 KiB
test_16.txt	AC	33 ms	55020 KiB
test_17.txt	AC	191 ms	73140 KiB
test_18.txt	AC	120 ms	71332 KiB
test_19.txt	AC	56 ms	56504 KiB
test_20.txt	AC	155 ms	81200 KiB
test_21.txt	AC	185 ms	81256 KiB
test_22.txt	AC	210 ms	81212 KiB
test_23.txt	AC	156 ms	81244 KiB
test_24.txt	AC	253 ms	81328 KiB
test_25.txt	AC	177 ms	81324 KiB
test_26.txt	AC	243 ms	81120 KiB
test_27.txt	AC	192 ms	81280 KiB
test_28.txt	AC	180 ms	81120 KiB
test_29.txt	AC	145 ms	81220 KiB
test_30.txt	AC	20 ms	50728 KiB
test_31.txt	AC	20 ms	50780 KiB
test_32.txt	AC	20 ms	50676 KiB
test_33.txt	AC	20 ms	50736 KiB
test_34.txt	AC	20 ms	50720 KiB
test_35.txt	AC	20 ms	50720 KiB
test_36.txt	AC	20 ms	50576 KiB
test_37.txt	AC	20 ms	50744 KiB
test_38.txt	AC	20 ms	50712 KiB
test_39.txt	AC	20 ms	50696 KiB
test_40.txt	AC	20 ms	50584 KiB
test_41.txt	AC	20 ms	50744 KiB
test_42.txt	AC	20 ms	50720 KiB
test_43.txt	AC	20 ms	50788 KiB
test_44.txt	AC	20 ms	50700 KiB
test_45.txt	AC	20 ms	50676 KiB
test_46.txt	AC	20 ms	50756 KiB
test_47.txt	AC	20 ms	50708 KiB
test_48.txt	AC	20 ms	50708 KiB
test_49.txt	AC	20 ms	50792 KiB