QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625709#8236. Snake MovezxkWA 659ms162592kbC++171.9kb2024-10-09 20:35:272024-10-09 20:35:27

Judging History

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

  • [2024-10-09 20:35:27]
  • 评测
  • 测评结果:WA
  • 用时:659ms
  • 内存:162592kb
  • [2024-10-09 20:35:27]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef unsigned long long ULL;

const int N = 3010, inf = 1e18;

int n, m, k;
char g[N][N];
int d[N][N], dist[N][N]; // 离尾巴的距离, 最短路
bool vis[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs(int x, int y)
{
	queue<array<int, 3>> q1;
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int,3>> > q2;
	dist[x][y] = 0;
	q1.push({0, x, y});
	vis[x][y] = true;
	while (q1.size())
	{
		array<int, 3> tmp;
		if (q2.size() && q2.top()[0] <= q1.front()[0]) {tmp = q2.top(); q2.pop();}
		else {tmp = q1.front(); q1.pop();}
		auto [cnt, x, y] = tmp;
		for (int i = 0; i < 4; i ++ )
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (nx <= 0 || nx > n || ny <= 0 || ny > m || vis[nx][ny] || g[nx][ny] == '#') continue;
			if (d[nx][ny] != -1 && cnt+1 < d[nx][ny])
			{
				q2.push({d[nx][ny], nx, ny});
				dist[nx][ny] = d[nx][ny];
				vis[nx][ny] = true;
			}
			else
			{
				q1.push({cnt+1, nx, ny});
				dist[nx][ny] = cnt + 1;
				vis[nx][ny] = true;
			}
		}
	}
}

signed main()
{
	cin >> n >> m >> k;
	PII start;
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			dist[i][j] = inf;
			d[i][j] = -1;
		}
	for (int i = 0; i < k; i ++ )
	{
		int x, y;
		cin >> x >> y;
		d[x][y] = k - i;
		if (i == 0) start = {x, y};
	}
	
	for (int i = 1; i <= n; i ++ ) 
		for (int j = 1; j <= m; j ++ )
			cin >> g[i][j];
	
	bfs(start.first, start.second);
	
	// for (int i = 1; i <= n; i ++ )
	// {
		// for (int j = 1; j <= m; j ++ )
		// {
			// cout << dist[i][j] << ' ';
		// }
		// cout << '\n';
	// }
	
	unsigned long long ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			if (dist[i][j] != inf) ans += 1ull * dist[i][j] * dist[i][j];
		}
	}
	
	cout << ans << '\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9760kb

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: 2ms
memory: 9760kb

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: 2ms
memory: 9716kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 655ms
memory: 162592kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 659ms
memory: 158660kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 268ms
memory: 154168kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 255ms
memory: 155024kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 616ms
memory: 158212kb

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: 650ms
memory: 162524kb

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: 261ms
memory: 154252kb

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: 265ms
memory: 149756kb

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'