QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548991 | #8236. Snake Move | enar | RE | 527ms | 73960kb | C++20 | 2.1kb | 2024-09-05 22:54:13 | 2024-09-05 22:54:13 |
Judging History
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 ........................................................#............................#........................................................................................................