QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#549002 | #8236. Snake Move | enar | WA | 511ms | 73788kb | C++20 | 1.8kb | 2024-09-05 23:17:05 | 2024-09-05 23:17:07 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int INF = 1E9;
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, INF));
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 == '#');
}
}
auto cmp = [&f](const std::pair<int, int> &pa, const std::pair<int, int> &pb) {
return f[pa.first][pa.second] > f[pb.first][pb.second];
};
std::queue<std::pair<int, int>> q;
std::priority_queue<std::pair<int, int>> tq;
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);
}
}
while(!q.empty() || !tq.empty()) {
std::pair<int, int> t;
if(q.empty() || (!tq.empty() && cmp(q.front(), tq.top()))) {
t = tq.top();
tq.pop();
} else {
t = q.front();
q.pop();
}
const auto &[x, y] = t;
for(const auto &[dx, dy] : std::vector<std::pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
int xx = x + dx, yy = y + dy;
if(1 <= xx && xx <= n && 1 <= yy && yy <= m && v[xx][yy] != -1 && f[xx][yy] == INF) {
if(v[xx][yy] >= 2) {
f[xx][yy] = std::max(f[x][y] + 1, k - v[xx][yy] + 1);
tq.emplace(xx, yy);
} else {
f[xx][yy] = f[x][y] + 1;
q.emplace(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] == INF ? 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: 3556kb
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: 3792kb
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: 3620kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 408ms
memory: 71880kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 511ms
memory: 72112kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 74ms
memory: 73788kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 67ms
memory: 71588kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: -100
Wrong Answer
time: 436ms
memory: 71808kb
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:
49803365646186
result:
wrong answer 1st lines differ - expected: '49803365625286', found: '49803365646186'