QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360895#8236. Snake Movewhsyhyyh#WA 242ms144600kbC++141.9kb2024-03-22 14:14:452024-03-22 14:14:47

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 14:14:47]
  • 评测
  • 测评结果:WA
  • 用时:242ms
  • 内存:144600kb
  • [2024-03-22 14:14:45]
  • 提交

answer

#include<bits/stdc++.h>
#define N 3010
#define uLL unsigned long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int rd() {
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return res*f;
}
int n,m,K;
int mp[N][N],snk[N][2],dis[N][N];
char ch[N];
int qu[N*N*2][2],hd=1,tl;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs() {
    memset(dis,63,sizeof(dis));
    dis[snk[1][0]][snk[1][1]]=0,qu[++tl][0]=snk[1][0],qu[tl][1]=snk[1][1];
    int x,y,now;
    while(hd<=tl) {
        x=qu[hd][0],y=qu[hd++][1];
        now=dis[x][y];
        int wasx=x,wasy=y;
        if(now<K&&(hd==1||now!=dis[qu[hd-2][0]][qu[hd-2][1]])) {
            x=snk[K-now][0],y=snk[K-now][1];
            for(int i=0,xx,yy;i<=3;i++) {
                xx=x+dx[i],yy=y+dy[i];
                if(dis[xx][yy]<0x3f3f3f3f) {
                    if(dis[x][y]>now+1) {
                        dis[x][y]=now+1;
                        qu[++tl][0]=x,qu[tl][1]=y;
                    }
                }
            }
        }
        x=wasx,y=wasy;
        for(int i=0,xx,yy;i<=3;i++) {
            xx=x+dx[i],yy=y+dy[i];
            if(mp[xx][yy]<=dis[x][y]+1) {
                if(dis[xx][yy]>dis[x][y]+1) {
                    dis[xx][yy]=dis[x][y]+1;
                    qu[++tl][0]=xx,qu[tl][1]=yy;
                }
            }
        }
    }
}
int main() {
    n=rd(),m=rd(),K=rd();
    memset(mp,63,sizeof(mp));
    rep(i,1,K) snk[i][0]=rd(),snk[i][1]=rd();
    rep(i,1,n) {
        scanf("%s",ch+1);
        rep(j,1,m) if(ch[j]=='.') mp[i][j]=0;
    }
    rep(i,1,K) mp[snk[i][0]][snk[i][1]]=K-i+1;
    bfs();
    uLL ans=0;
    rep(i,1,n) rep(j,1,m) if(dis[i][j]<0x3f3f3f3f) ans+=1ull*dis[i][j]*dis[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: 76188kb

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: 75364kb

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: 7ms
memory: 74796kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 96ms
memory: 144600kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 228ms
memory: 124144kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 47ms
memory: 75620kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 42ms
memory: 74824kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 96ms
memory: 142516kb

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: 242ms
memory: 124000kb

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: 50ms
memory: 76544kb

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: 44ms
memory: 75028kb

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:

170

result:

wrong answer 1st lines differ - expected: '2705', found: '170'