QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#324469 | #8236. Snake Move | ucup-team484# | WA | 893ms | 74480kb | C++17 | 1.5kb | 2024-02-10 19:49:03 | 2024-02-10 19:49:04 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef unsigned long long ll;
const int mod = 1e9 + 7;
const int N = 3e3 + 5;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
vector<pair<int, int>> a(k);
vector<vector<int>> ans(n, vector<int>(m, mod)), vis(n, vector<int>(m, 0));
for (int i = 0; i < k; i++) {
cin >> a[i].first >> a[i].second;
a[i].first--;
a[i].second--;
vis[a[i].first][a[i].second] = i;
}
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++)
if (s[j] == '#')
vis[i][j] = -1;
}
ans[a[0].first][a[0].second] = 0;
priority_queue<pair<int, pair<int, int>>> q;
auto upd = [&](auto p, int d) {
for (int i = 0; i < 4; i++) {
int nx = p.first + dx[i];
int ny = p.second + dy[i];
if (nx < 0 || ny < 0 || n <= nx || m <= ny || vis[nx][ny] == -1)
continue;
if ((vis[nx][ny] + d + 1 >= k || vis[nx][ny] == 0) && ans[nx][ny] > d + 1) {
ans[nx][ny] = d + 1;
q.push(make_pair(-d - 1, make_pair(nx, ny)));
}
}
};
q.push(make_pair(0, a[0]));
int lo = 0;
ll res = 0;
while (!q.empty()) {
auto [d, p] = q.top();
q.pop();
d = -d;
if (p != a[0] && d != ans[p.first][p.second])
continue;
if (p != a[0])
res += (ll)d * (ll)d;
else if (d == lo && lo + 1 < k)
q.push(make_pair(-(++lo), a[0]));
upd(p, d);
}
cout << res << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3744kb
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: 3552kb
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: 3608kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 884ms
memory: 71848kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 833ms
memory: 71876kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 43ms
memory: 74180kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 40ms
memory: 71848kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 893ms
memory: 72096kb
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: 848ms
memory: 74480kb
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: -100
Wrong Answer
time: 44ms
memory: 71804kb
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:
41915
result:
wrong answer 1st lines differ - expected: '40571', found: '41915'