QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#620501#8236. Snake MoveHide_In_The_ShadowWA 355ms118540kbC++232.4kb2024-10-07 18:37:472024-10-07 18:37:48

Judging History

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

  • [2024-10-07 18:37:48]
  • 评测
  • 测评结果:WA
  • 用时:355ms
  • 内存:118540kb
  • [2024-10-07 18:37:47]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define fio std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int,int>
using namespace std;
template<typename T>void read(T &x){
    x=0;
    char c=getchar();
    T ret=0;
    while(!isdigit(c))ret|=!(c^'-'),c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(ret)x=(~x)+1;
}
template<typename T,typename ...Args>
void read(T &x,Args &...xs){
    read(x);read(xs...);
}
template<typename T>void print(T x){
    if(x<0)putchar('-'),x=(~x)+1;
    if(x>9)print(x/10);
    putchar((x-x/10*10)^48);
}
template<typename T>void wr1(T x){
    print(x);putchar(' ');
}
template<typename T>void wr2(T x){
    print(x);putchar('\n');
}
const int N=3005;
int n,m,k,c1[]={1,0,-1,0},c2[]={0,1,0,-1},snac[N][N],sx,sy;
unsigned ll dis[N][N];
char mp[N][N];
bool chek(int x,int y) {
    if(x<1||y<1||x>n||y>m||mp[x][y]=='#')return 0;
    return 1;
}
queue<pii>q1,q2;
int main(){
    read(n,m,k);
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            dis[i][j]=LONG_LONG_MAX;
            snac[i][j]=k;
        }
    }
    for(int i=1;i<=k;++i){
        int x,y;
        read(x,y);
        if(!sx)sx=x;
        if(!sy)sy=y;
        snac[x][y]=i;
    }
    for(int i=1;i<=n;++i) {
        scanf("%s",mp[i]+1);
    }
    dis[sx][sy]=0;
    q1.push({sx,sy});
    while(!q1.empty()){
        int x=q1.front().first,y=q1.front().second;
        int X=0,Y=0;
        if(!q2.empty()) {
            X=q2.front().first,Y=q2.front().second;
            if(dis[x][y]<dis[X][Y])q1.pop();
            else q2.pop(),x=X,y=Y;
        }
        if(!(X|Y))q1.pop();
        for(int i=0;i<=3;++i) {
            X=x+c1[i],Y=y+c2[i];
            if(chek(X,Y)) {
                if(dis[X][Y]>dis[x][y]+1) {
                    if(dis[x][y]>=k-snac[X][Y]) {
                        dis[X][Y]=dis[x][y]+1;
                        q1.push({X,Y});
                    }
                    else {
                        dis[X][Y]=k-snac[X][Y]+1;
                        q2.push({X,Y});
                    }
                }
            }
        }
    }
    unsigned ll ans=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            if(dis[i][j]>=LONG_LONG_MAX)continue;
            ans+=dis[i][j]*dis[i][j];
        }
    }
    print(ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8064kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 259ms
memory: 118296kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 340ms
memory: 114940kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 23ms
memory: 118324kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 24ms
memory: 118540kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 234ms
memory: 115128kb

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

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

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

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:

251

result:

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