QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661569#8236. Snake MoveLemonWA 1020ms952640kbC++142.1kb2024-10-20 16:53:372024-10-20 16:53:37

Judging History

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

  • [2024-10-20 16:53:37]
  • 评测
  • 测评结果:WA
  • 用时:1020ms
  • 内存:952640kb
  • [2024-10-20 16:53:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=8e7;
const int N=9e6+5;
const ull inf=1e18;
int hd[N],cnt,n,m,k,stx,sty,vis[N];
char s[3005][3005];
ull dis[N],len[N];
ull ans;
struct edge{
    int u,to,nxt;
}e[maxn];
void add(int u,int v){
    e[++cnt].nxt=hd[u];
    e[cnt].to=v;
    e[cnt].u=u;
    hd[u]=cnt;
}
int pos(int x,int y){
    return (x-1)*m+y;
}
queue<int>q;
void bfs(int x,int y){
    q.push(pos(x,y));
    vis[pos(stx,sty)]=1;
    dis[pos(stx,sty)]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]>=max(dis[u]+1,len[v]+1)){
                dis[v]=max(dis[u]+1,len[v]+1);
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dis[pos(i,j)]=inf;
        }
    }
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(i==1) stx=x,sty=y;
        len[pos(x,y)]=k-i;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#') continue;
            if(s[i-1][j]=='.'){
                add(pos(i,j),pos(i-1,j));
                add(pos(i-1,j),pos(i,j));
            }
            if(s[i][j-1]=='.'){
                add(pos(i,j),pos(i,j-1));
                add(pos(i,j-1),pos(i,j));
            }
            if(s[i+1][j]=='.'){
                add(pos(i,j),pos(i+1,j));
                add(pos(i+1,j),pos(i,j));
            }
            if(s[i][j+1]=='.'){
                add(pos(i,j),pos(i,j+1));
                add(pos(i,j+1),pos(i,j));
            }
        }
    }
    bfs(stx,sty);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dis[pos(i,j)]==inf) continue;
            ans+=(dis[pos(i,j)]*dis[pos(i,j)]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 13952kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 1020ms
memory: 950932kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 817ms
memory: 546152kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 130ms
memory: 330784kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 63ms
memory: 195256kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 946ms
memory: 952640kb

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: -100
Wrong Answer
time: 766ms
memory: 560712kb

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:

22509095749317

result:

wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'