QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611108 | #8236. Snake Move | zhz_vite | WA | 335ms | 62336kb | C++14 | 2.4kb | 2024-10-04 19:23:56 | 2024-10-04 19:23:57 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<queue>
using namespace std;
const int N = 3010;
const int K = 100005;
char a[N][N];
int shu[K], heng[K];
int n, m, k;
int f[N][N];
int rk[N][N];
typedef pair<int, int> pii;
queue<pii> q;
bool vis[N][N];
priority_queue<pii, vector<pii>, greater<pii>> hp;
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k;i++)
scanf("%d %d", &heng[i], &shu[i]);
for (int i = 1; i <= n;i++)
scanf("%s ", a[i] + 1);
memset(f, -1, sizeof f);
for (int i = 2; i <= k;i++)
a[heng[i]][shu[i]] = 'X', rk[heng[i]][shu[i]] = i;
// for (int i = 1; i <= n;i++)
// {
// for (int j = 1; j <= m;j++){
// cout << a[i][j];
// }
// cout << endl;
// }
f[heng[1]][shu[1]] = 0;
q.push(pii(heng[1], shu[1]));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 1; i <= 4;i++){
int nx = x + dx[i], ny = y + dy[i];
if(nx<1||ny<1||nx>n||ny>m)
continue;
if(vis[nx][ny])
continue;
if(a[nx][ny]=='#')
continue;
else if(a[nx][ny]=='.'&&f[nx][ny]==-1){
f[nx][ny] = f[x][y] + 1;
q.push(pii(nx, ny));
}
else {
if(!vis[nx][ny])
hp.push(pii(max(f[x][y] + 1, k - rk[nx][ny] + 1), rk[nx][ny]));
}
vis[nx][ny] = true;
}
if(q.empty()&&!hp.empty()){
int dis = hp.top().first, id = hp.top().second;
hp.pop();
f[heng[id]][shu[id]]=dis;
q.push(pii(heng[id], shu[id]));
}
else {
int tx = q.front().first, ty = q.front().second;
if(!hp.empty()&&hp.top().first<=f[tx][ty]){
int dis = hp.top().first, id = hp.top().second;
f[heng[id]][shu[id]] = dis;
q.push(pii(heng[id], shu[id]));
hp.pop();
}
}
}
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 += 1ull*f[i][j] * f[i][j];
}
printf("%llu", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 44840kb
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: 45020kb
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: 42796kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 198ms
memory: 60268kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 335ms
memory: 60104kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 26ms
memory: 52168kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 18ms
memory: 51872kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 209ms
memory: 60472kb
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: 331ms
memory: 62312kb
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: 19ms
memory: 53908kb
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: 0
Accepted
time: 27ms
memory: 54388kb
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:
2705
result:
ok single line: '2705'
Test #12:
score: 0
Accepted
time: 216ms
memory: 62268kb
input:
3000 3000 100 2573 1917 2572 1917 2572 1916 2573 1916 2574 1916 2574 1915 2573 1915 2572 1915 2571 1915 2571 1914 2570 1914 2570 1915 2569 1915 2569 1916 2568 1916 2568 1917 2569 1917 2570 1917 2570 1916 2571 1916 2571 1917 2571 1918 2570 1918 2569 1918 2569 1919 2570 1919 2571 1919 2571 1920 2572 1...
output:
41693682087973
result:
ok single line: '41693682087973'
Test #13:
score: 0
Accepted
time: 305ms
memory: 62260kb
input:
3000 2900 56 923 228 922 228 921 228 920 228 919 228 919 227 919 226 920 226 920 227 921 227 922 227 922 226 922 225 921 225 921 224 921 223 920 223 920 222 920 221 921 221 921 222 922 222 923 222 924 222 925 222 925 223 924 223 923 223 922 223 922 224 923 224 923 225 924 225 924 224 925 224 925 225...
output:
36262204093655
result:
ok single line: '36262204093655'
Test #14:
score: 0
Accepted
time: 20ms
memory: 54804kb
input:
2900 3000 100 2357 817 2357 818 2357 819 2358 819 2359 819 2360 819 2360 820 2361 820 2361 819 2361 818 2360 818 2360 817 2361 817 2362 817 2362 818 2363 818 2364 818 2365 818 2365 817 2364 817 2363 817 2363 816 2363 815 2362 815 2362 814 2361 814 2361 815 2360 815 2360 816 2359 816 2358 816 2358 81...
output:
4878972
result:
ok single line: '4878972'
Test #15:
score: 0
Accepted
time: 20ms
memory: 51560kb
input:
3000 3000 97 2987 2472 2986 2472 2986 2471 2985 2471 2985 2470 2985 2469 2984 2469 2983 2469 2983 2468 2982 2468 2981 2468 2980 2468 2979 2468 2978 2468 2977 2468 2977 2469 2978 2469 2978 2470 2977 2470 2976 2470 2976 2471 2977 2471 2977 2472 2978 2472 2978 2473 2977 2473 2976 2473 2976 2472 2975 24...
output:
1992372
result:
ok single line: '1992372'
Test #16:
score: 0
Accepted
time: 194ms
memory: 62264kb
input:
3000 2900 22 2673 1308 2673 1309 2673 1310 2672 1310 2672 1309 2672 1308 2672 1307 2671 1307 2671 1306 2671 1305 2672 1305 2672 1306 2673 1306 2674 1306 2674 1305 2675 1305 2675 1306 2675 1307 2675 1308 2674 1308 2674 1307 2673 1307 ......................................................................
output:
39910190747333
result:
ok single line: '39910190747333'
Test #17:
score: 0
Accepted
time: 322ms
memory: 61968kb
input:
2900 3000 72 820 2426 820 2427 820 2428 820 2429 820 2430 821 2430 821 2429 821 2428 822 2428 822 2429 822 2430 823 2430 824 2430 824 2429 824 2428 825 2428 825 2427 824 2427 824 2426 824 2425 825 2425 825 2426 826 2426 827 2426 828 2426 828 2427 829 2427 829 2426 830 2426 830 2427 830 2428 830 2429...
output:
30022933538350
result:
ok single line: '30022933538350'
Test #18:
score: 0
Accepted
time: 30ms
memory: 53932kb
input:
3000 3000 77 2008 1630 2007 1630 2007 1629 2007 1628 2006 1628 2005 1628 2004 1628 2004 1629 2003 1629 2002 1629 2001 1629 2001 1628 2000 1628 2000 1627 2000 1626 1999 1626 1999 1627 1999 1628 1999 1629 1999 1630 1999 1631 1999 1632 2000 1632 2000 1633 2000 1634 2001 1634 2001 1635 2001 1636 2002 16...
output:
385875
result:
ok single line: '385875'
Test #19:
score: 0
Accepted
time: 26ms
memory: 53908kb
input:
3000 2900 31 1343 2185 1342 2185 1342 2184 1341 2184 1341 2185 1341 2186 1341 2187 1340 2187 1340 2188 1339 2188 1338 2188 1337 2188 1336 2188 1336 2187 1337 2187 1337 2186 1337 2185 1337 2184 1338 2184 1338 2183 1337 2183 1336 2183 1335 2183 1335 2184 1334 2184 1334 2185 1334 2186 1335 2186 1335 21...
output:
97830
result:
ok single line: '97830'
Test #20:
score: 0
Accepted
time: 197ms
memory: 60300kb
input:
2900 3000 113 551 1058 551 1057 552 1057 552 1056 553 1056 553 1055 552 1055 551 1055 551 1054 552 1054 552 1053 552 1052 552 1051 551 1051 551 1052 551 1053 550 1053 550 1052 549 1052 549 1051 548 1051 548 1050 547 1050 547 1051 546 1051 545 1051 545 1050 545 1049 545 1048 544 1048 544 1049 544 105...
output:
35257969420026
result:
ok single line: '35257969420026'
Test #21:
score: 0
Accepted
time: 275ms
memory: 62336kb
input:
3000 3000 43 734 2607 733 2607 733 2608 733 2609 732 2609 732 2610 733 2610 734 2610 734 2609 734 2608 735 2608 735 2607 735 2606 735 2605 736 2605 736 2604 735 2604 734 2604 734 2603 735 2603 735 2602 735 2601 734 2601 734 2602 733 2602 733 2603 732 2603 731 2603 730 2603 730 2604 730 2605 730 2606...
output:
44813406952069
result:
ok single line: '44813406952069'
Test #22:
score: 0
Accepted
time: 310ms
memory: 62336kb
input:
3000 2900 31 2017 1649 2016 1649 2016 1648 2016 1647 2017 1647 2017 1646 2017 1645 2016 1645 2015 1645 2014 1645 2014 1644 2015 1644 2015 1643 2014 1643 2013 1643 2013 1644 2013 1645 2013 1646 2014 1646 2014 1647 2014 1648 2013 1648 2013 1649 2014 1649 2014 1650 2015 1650 2015 1649 2015 1648 2015 16...
output:
21058834151672
result:
ok single line: '21058834151672'
Test #23:
score: 0
Accepted
time: 308ms
memory: 62308kb
input:
2900 3000 28 1314 1304 1313 1304 1312 1304 1312 1305 1311 1305 1311 1304 1311 1303 1310 1303 1310 1304 1310 1305 1310 1306 1311 1306 1311 1307 1312 1307 1312 1308 1312 1309 1313 1309 1313 1310 1312 1310 1311 1310 1311 1309 1311 1308 1310 1308 1309 1308 1309 1309 1309 1310 1310 1310 1310 1309 ..##..#...
output:
17072462334840
result:
ok single line: '17072462334840'
Test #24:
score: -100
Wrong Answer
time: 24ms
memory: 53620kb
input:
3000 3000 150 1859 868 1860 868 1860 867 1859 867 1859 866 1859 865 1858 865 1858 866 1857 866 1857 865 1856 865 1856 864 1856 863 1856 862 1856 861 1856 860 1856 859 1857 859 1857 858 1858 858 1859 858 1859 859 1858 859 1858 860 1859 860 1860 860 1860 861 1859 861 1858 861 1858 862 1858 863 1857 86...
output:
450202064
result:
wrong answer 1st lines differ - expected: '450198912', found: '450202064'