QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#342946#8236. Snake Moveucup-team191#WA 437ms118572kbC++233.0kb2024-03-01 19:57:142024-03-01 19:57:14

Judging History

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

  • [2024-03-01 19:57:14]
  • 评测
  • 测评结果:WA
  • 用时:437ms
  • 内存:118572kb
  • [2024-03-01 19:57:14]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pii;
typedef unsigned long long ull;

const int N = 3050;
const int px[4] = {0, 0, 1, -1};
const int py[4] = {1, -1, 0, 0};

int n, m, k;
vector < pii > zm;
int S[N][N], dis[N][N], pos[N][N], treba[N][N], ans[N][N];
queue < pii > Q;

int main(){
	memset(dis, -1, sizeof(dis));
	memset(treba, -1, sizeof(treba));
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> k;
	for(int i = k - 1;i >= 0;i--) {
		int x, y; cin >> x >> y;
		x--, y--; 
		if(i + 1 < k) {
			pos[x][y] = k - i;
			treba[x][y] = max(k - 2, 0) + (k - i - 1); 	
		}	
		zm.PB({x, y});
	}
	reverse(zm.begin(), zm.end());
	for(int i = 0;i < n;i++) {
		string tmp; cin >> tmp;
		for(int j = 0;j < m;j++)
			S[i][j] = (tmp[j] == '#');
	}
	int hx = zm.back().X, hy = zm.back().Y;
	dis[hx][hy] = 0; Q.push({hx, hy});
	for(;!Q.empty();Q.pop()) {
		int cx = Q.front().X, cy = Q.front().Y;
		//cout << cx << " " << cy << endl;
		for(int t = 0;t < 4;t++) {
			int nx = cx + px[t], ny = cy + py[t];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || S[nx][ny]) continue;
			if(pos[nx][ny]) {
				if(cx != hx || cy != hy || pos[nx][ny] != 2) {
					treba[nx][ny] = min(treba[nx][ny], max(k - pos[nx][ny] - dis[cx][cy], 0) + dis[cx][cy] + 1);
				//	cout << k << " " << pos[nx][ny] << " " << dis[cx][cy] << endl;
				//	cout << " T " << treba[nx][ny] << endl;
				//	cout << nx << " " << ny << endl;
				}
			} else if(dis[nx][ny] == -1){
				dis[nx][ny] = dis[cx][cy] + 1;
				Q.push({nx, ny});
			}
		}
	}
	for(int i = 1;i + 1 < k;i++) {
		treba[zm[i].X][zm[i].Y] = min(treba[zm[i].X][zm[i].Y], treba[zm[i - 1].X][zm[i - 1].Y] + 1);
	}
	for(int i = k - 3;i >= 0;i--) {
		treba[zm[i].X][zm[i].Y] = min(treba[zm[i].X][zm[i].Y], treba[zm[i + 1].X][zm[i + 1].Y] + 1);
	}
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < m;j++) {
			if(pos[i][j]) {
				Q.push({i, j});
			} else {
				treba[i][j] = -1;
			}
		}
	}
	for(;!Q.empty();Q.pop()) {
		int cx = Q.front().X, cy = Q.front().Y;
		for(int k = 0;k < 4;k++) {
			int nx = cx + px[k], ny = cy + py[k];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || S[nx][ny] || treba[nx][ny] != -1) continue;
			treba[nx][ny] = treba[cx][cy] + 1;
			Q.push({nx, ny});
			
		}
	}
	ull ans = 0;
	for(int i = 0;i < n;i++) {
		for(int j = 0;j < m;j++) {
			if(dis[i][j] != -1 && treba[i][j] != -1) {
				ull x = min(dis[i][j], treba[i][j]);
			//	printf("%d ", min(dis[i][j], treba[i][j]));
				ans += x * x;
			} else if(dis[i][j] != -1) {
				ans += (ull)dis[i][j] * dis[i][j];
			//	printf("%d ", max(dis[i][j], treba[i][j]));
			} else if(treba[i][j] != -1){
				ans += (ull)treba[i][j] * treba[i][j];
			//	printf("%d ", max(dis[i][j], treba[i][j]));
			} else {
			//	printf("x ");
			}
		}
	//	printf("\n");
	}
	//printf("%llu\n", ans);
	cout << ans << endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 79404kb

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: 79592kb

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: 0ms
memory: 81684kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 141ms
memory: 115604kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 253ms
memory: 113524kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 26ms
memory: 115112kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 20ms
memory: 116636kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 341ms
memory: 117280kb

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: -100
Wrong Answer
time: 437ms
memory: 118572kb

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:

22509095749345

result:

wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749345'