QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#775903 | #8236. Snake Move | dodola | WA | 1054ms | 96804kb | C++17 | 2.8kb | 2024-11-23 17:01:10 | 2024-11-23 17:01:10 |
Judging History
answer
#include <bits/stdc++.h>
#include <functional>
#include <iomanip>
#include <ios>
#include <queue>
#include <utility>
#include <vector>
#define x first
#define y second
using namespace std;
typedef double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 50;
const ll inf = 0x3f3f3f3f3f3f;
const vector<pll> dxy = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
ll n, m, k;
char maz[3090][3090];
ull dis[3090][3090];
bool vis[3090][3090];
map<pll, ll> body;
bool check(pll &p) { return p.x >= 1 && p.x <= n && p.y >= 1 && p.y <= m; };
void dij(pll st) {
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<>> q;
for (auto [pi, di] : body) {
dis[pi.x][pi.y] = k - 2 + k - di;
if (st != pi)
q.push({dis[pi.x][pi.y], pi});
}
q.push({0, st});
dis[st.x][st.y] = 0;
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cout << dis[i][j] << " \n"[j == m];
// }
// }
while (!q.empty()) {
auto [d, p] = q.top();
q.pop();
if (vis[p.x][p.y])
continue;
vis[p.x][p.y] = true;
for (auto [dx, dy] : dxy) {
pll pi = {p.x + dx, p.y + dy};
if (!check(pi))
continue;
if (dis[pi.x][pi.y] == 0)
continue;
if (vis[pi.x][pi.y])
continue;
if (body.count(pi) == 0) {
if (dis[pi.x][pi.y] > (ull)d + 1) {
dis[pi.x][pi.y] = d + 1;
q.push({d + 1, pi});
}
} else {
if (body[pi] <= (ull)d + 1 && dis[pi.x][pi.y] > (ull)d + 1) {
dis[pi.x][pi.y] = d + 1;
q.push({dis[pi.x][pi.y], pi});
}
}
}
}
}
void solve() {
cin >> n >> m >> k;
body.clear();
pll st;
for (ll i = k - 1; i >= 0; i--) {
pll p;
cin >> p.x >> p.y;
if (i == k - 1) {
st = p;
body[p] = 0;
} else {
body[p] = i + 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> maz[i][j];
vis[i][j] = false;
if (maz[i][j] == '#') {
dis[i][j] = 0;
vis[i][j] = true;
} else {
dis[i][j] = inf;
}
}
}
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cout << dis[i][j] << " \n"[j == m];
// }
// }
dij(st);
ull ans = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
ull d = dis[i][j];
if (d == inf)
d = 0;
ans += d * d;
// cout << d << " \n"[j == m];
}
}
cout << fixed << setprecision(0) << ans << '\n';
}
void init() {
// init_primes();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
init();
int _t = 1;
// cin >> _t;
// cin.get();
while (_t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9684kb
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: 7920kb
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: 1ms
memory: 7652kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 998ms
memory: 96636kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 894ms
memory: 94572kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 183ms
memory: 96804kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 141ms
memory: 96788kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 1054ms
memory: 94244kb
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: 954ms
memory: 96740kb
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: 182ms
memory: 96508kb
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'