QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#342946 | #8236. Snake Move | ucup-team191# | WA | 437ms | 118572kb | C++23 | 3.0kb | 2024-03-01 19:57:14 | 2024-03-01 19:57:14 |
Judging History
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'