QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548991#8236. Snake MoveenarRE 527ms73960kbC++202.1kb2024-09-05 22:54:132024-09-05 22:54:13

Judging History

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

  • [2024-09-05 22:54:13]
  • 评测
  • 测评结果:RE
  • 用时:527ms
  • 内存:73960kb
  • [2024-09-05 22:54:13]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;
constexpr int MAXN = 1E9;

struct node {
	int x, y, dis;
	bool operator<(const node &other) const {
		return dis > other.dis;
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, k;
	std::cin >> n >> m >> k;
	std::vector<std::vector<int>> v(n + 1, std::vector<int>(m + 1));
	std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1, MAXN));
	std::vector<std::pair<int, int>> vec(k + 1);
	for(int i = 1; i <= k; ++i) {
		auto &[x, y] = vec[i]; 
		std::cin >> x >> y;
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			char ch;
			std::cin >> ch;
			v[i][j] = -1 * (ch == '#');
		}
	}
	std::queue<node> q;
	std::deque<node> dq;
	for(int i = 1; i <= k; ++i) {
		const auto &[x, y] = vec[i];
		v[x][y] = i;
		if(i == 1) {
			f[x][y] = 0;
			q.emplace(x, y, 0);
		}
	}
	while(!q.empty() || !dq.empty()) {
		node t;
		if(q.empty() || (!dq.empty() && dq.front().dis < q.front().dis)) {
			t = dq.front();
			dq.pop_front();
		} else {
			t = q.front();
			q.pop();
		}
		const auto &[x, y, dis] = t;
		if(dis != f[x][y]) continue;
		for(auto [dx, dy] : std::vector<std::pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
			int xx = x + dx;
			int yy = y + dy;
			if(1 <= xx && xx <= n && 1 <= yy && yy <= m && v[xx][yy] != -1) {
				if(v[xx][yy] >= 2) {
					int val = std::max(f[x][y] + 1, k - v[xx][yy] + 1);
					if(val < f[xx][yy]) {
						f[xx][yy] = val;
						if(dq.empty()) {
							dq.emplace_front(xx, yy, f[xx][yy]);
						} else if(f[xx][yy] <= dq.front().dis) {
							dq.emplace_front(xx, yy, f[xx][yy]);
						} else {
							assert(f[xx][yy] > dq.back().dis);
							dq.emplace_back(xx, yy, f[xx][yy]);
						}
					}
				} else if(f[x][y] + 1 < f[xx][yy]) {
					f[xx][yy] = f[x][y] + 1;
					q.emplace(xx, yy, f[xx][yy]);
				}
			}
		}
	}
	unsigned long long ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			f[i][j] = (f[i][j] == MAXN ? 0 : f[i][j]);
			ans += 1ULL * f[i][j] * f[i][j];
		}
	}
	std::cout << ans << '\n';
	return 0;
}

详细

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 421ms
memory: 72136kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 527ms
memory: 71780kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 77ms
memory: 73960kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 76ms
memory: 71524kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Runtime Error

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:


result: