QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343360#8236. Snake Movezzuqy#WA 300ms175096kbC++141.7kb2024-03-02 14:26:582024-03-02 14:26:58

Judging History

你现在查看的是最新测评结果

  • [2024-03-02 14:26:58]
  • 评测
  • 测评结果:WA
  • 用时:300ms
  • 内存:175096kb
  • [2024-03-02 14:26:58]
  • 提交

answer

#include <bits/stdc++.h>
#define N 3006
#define K 1000006

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, k;
std::vector<std::pair<int, int> > wait[K];
int added[K];
char s[N][N];
int f[N][N], min[N][N], vis[N][N];

void bfs(int x, int y) {
	static std::pair<int, int> que[N * N];
	static int left, right;
	std::memset(f, -1, sizeof f);
	left = 1;
	right = 0;
	que[++right] = std::make_pair(x, y);
	f[x][y] = 0;
	vis[x][y] = 1;
	while (left <= right) {
		x = que[left].first;
		y = que[left].second;
		left++;
		if (f[x][y] <= k + 1 && !added[f[x][y] + 1]) {
			added[f[x][y] + 1] = 1;
			for (std::pair<int, int> o : wait[f[x][y] + 1]) {
				if (vis[o.first][o.second])
					continue;
				vis[o.first][o.second] = 1;
				que[++right] = o;
			}
		}
		for (int _x, _y, k = 0; k < 4; k++) {
			_x = x + dx[k];
			_y = y + dy[k];
			if (_x < 1 || _x > n || _y < 1 || _y > m)
				continue;
			if (s[_x][_y] == '#')
				continue;
			if (f[_x][_y] != -1 && f[_x][_y] <= f[x][y] + 1)
				continue;
			if (min[_x][_y] > f[x][y] + 1) {
				f[_x][_y] = min[_x][_y];
				wait[f[_x][_y]].push_back(std::make_pair(_x, _y));
			} else {
				f[_x][_y] = f[x][y] + 1;
				vis[_x][_y] = 1;
				que[++right] = std::make_pair(_x, _y);
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	int x, y;
	scanf("%d%d", &x, &y);
	for (int i = k - 1, x, y; i; i--) {
		scanf("%d%d", &x, &y);
		min[x][y] = i;
	}
	for (int i = 1; i <= n; i++)
		scanf("%s", s[i] + 1);
	bfs(x, y);
	unsigned long long ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (f[i][j] == -1)
				f[i][j] = 0;
			ans += (unsigned long long)f[i][j] * f[i][j];
		}
	printf("%llu", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 63052kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 63764kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 7ms
memory: 63676kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 207ms
memory: 175096kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 300ms
memory: 152972kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 27ms
memory: 71784kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 22ms
memory: 71888kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 219ms
memory: 172616kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 282ms
memory: 156140kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: 0
Accepted
time: 19ms
memory: 72448kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

40571

result:

ok single line: '40571'

Test #11:

score: -100
Wrong Answer
time: 28ms
memory: 73052kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

251

result:

wrong answer 1st lines differ - expected: '2705', found: '251'