QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661521#8236. Snake MoveLemonWA 1058ms949648kbC++142.6kb2024-10-20 16:38:252024-10-20 16:38:28

Judging History

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

  • [2024-10-20 16:38:28]
  • 评测
  • 测评结果:WA
  • 用时:1058ms
  • 内存:949648kb
  • [2024-10-20 16:38:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=8e7;
const int N=9e6;
const ll inf=1e18;
int hd[N],cnt,n,m,k,stx,sty,vis[9000005];
char s[3005][3005];
ll dis[9000005],len[9000005];
ll 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;
            //cout<<pos(i,j)<<' ';
        }
        //cout<<endl;
    }
    //cout<<f[1][1]<<endl;
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(i==1) stx=x,sty=y;
        //p[x][y]=1;
        //len[x][y]=k-i+1;
        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++){
            //cout<<s[i][j]<<' ';
            //if(p[i][j]) s[i][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));
            }
        }
        //cout<<endl;
    }
    //cout<<stx<<' '<<sty<<endl;
    bfs(stx,sty);
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         //dis[pos(i,j)]=max(dis[pos(i,j)],len[i][j]+1);
    //         //cout<<f[i][j]<<' ';
    //         cout<<dis[pos(i,j)]<<' ';
    //     }
    //     cout<<endl;
    // }
    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: 0ms
memory: 13896kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 1058ms
memory: 948976kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 731ms
memory: 541600kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 125ms
memory: 326648kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 59ms
memory: 190268kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

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

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

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'