QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#343353 | #8236. Snake Move | zzuqy# | WA | 233ms | 143668kb | C++14 | 1.6kb | 2024-03-02 14:22:11 | 2024-03-02 14:22:12 |
Judging History
answer
#include <bits/stdc++.h>
#define N 3006
#define K 1000006
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, k;
std::vector<std::pair<int, int> > wait[K];
int added[K];
char s[N][N];
int f[N][N], min[N][N];
void bfs(int x, int y) {
static std::pair<int, int> que[N * N];
static int left, right;
std::memset(f, -1, sizeof f);
left = 1;
right = 0;
que[++right] = std::make_pair(x, y);
f[x][y] = 0;
while (left <= right) {
x = que[left].first;
y = que[left].second;
left++;
if (f[x][y] <= k + 1 && !added[f[x][y] + 1]) {
added[f[x][y] + 1] = 1;
for (std::pair<int, int> o : wait[f[x][y] + 1]) {
que[++right] = o;
}
}
for (int _x, _y, k = 0; k < 4; k++) {
_x = x + dx[k];
_y = y + dy[k];
if (_x < 1 || _x > n || _y < 1 || _y > m)
continue;
if (s[_x][_y] == '#')
continue;
if (f[_x][_y] != -1)
continue;
if (min[_x][_y] > f[x][y] + 1) {
f[_x][_y] = min[_x][_y];
wait[f[_x][_y]].push_back(std::make_pair(_x, _y));
} else {
f[_x][_y] = f[x][y] + 1;
que[++right] = std::make_pair(_x, _y);
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
int x, y;
scanf("%d%d", &x, &y);
for (int i = k - 1, x, y; i; i--) {
scanf("%d%d", &x, &y);
min[x][y] = i;
}
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
bfs(x, y);
unsigned long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (f[i][j] == -1)
f[i][j] = 0;
ans += (unsigned long long)f[i][j] * f[i][j];
}
printf("%llu", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 67472kb
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: 3ms
memory: 67436kb
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: 3ms
memory: 67296kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 104ms
memory: 142216kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 233ms
memory: 122580kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 22ms
memory: 75588kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 21ms
memory: 75472kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 127ms
memory: 143668kb
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: 199ms
memory: 126852kb
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: 17ms
memory: 77568kb
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: 18ms
memory: 77708kb
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'