QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#370548#8236. Snake MoveArnold_6WA 349ms56396kbC++142.8kb2024-03-29 10:52:182024-03-29 10:52:36

Judging History

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

  • [2024-03-29 10:52:36]
  • 评测
  • 测评结果:WA
  • 用时:349ms
  • 内存:56396kb
  • [2024-03-29 10:52:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int n,m,k;
char g[3001][3001];
bool vis[3001][3001];
int d[3001][3001];
int body[3001][3001];
int hx,hy;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void dij()
{
    d[hx][hy]=0;
    // priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
    stack<pair<int,pair<int,int> > >q1;//body
    queue<pair<int,pair<int,int> > >q2;//notbody

    q1.push({0,{hx,hy}});
    while(q1.size() || q2.size())
    {
        int ans,x,y;
        if(q1.size() && q2.size())
        {
            if(q1.top().first<q2.front().first)
            {
                ans=q1.top().first;
                x=q1.top().second.first;
                y=q1.top().second.second;
                q1.pop();
            }
            else
            {
                ans=q2.front().first;
                x=q2.front().second.first;
                y=q2.front().second.second;
                q2.pop();
            }
        }
        
        else if(q1.size())
        {
            ans=q1.top().first;
            x=q1.top().second.first;
            y=q1.top().second.second;
            q1.pop();
        }

        else
        {
            ans=q2.front().first;
            x=q2.front().second.first;
            y=q2.front().second.second;
            q2.pop();
        }

        if(vis[x][y])continue;
        vis[x][y]=1;

        // cout<<endl<<x<<" "<<y<<" "<<ans<<endl;

        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny]=='#')continue;
            if(body[nx][ny]==0)
            {
                int tmp=d[x][y]+1;
                if(tmp<d[nx][ny])
                {
                    d[nx][ny]=d[x][y]+1;
                    q2.push({tmp,{nx,ny}});
                }
                
            }
            else
            {
                int tmp=max(d[x][y]+1,k-body[nx][ny]+1);
                if(tmp<d[nx][ny])
                {
                    d[nx][ny]=tmp;
                    q1.push({tmp,{nx,ny}});
                }
            }
            
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        body[x][y]=i;
        if(i==1)hx=x,hy=y;
    }
    for(int i=1;i<=n;i++)cin>>g[i]+1;
    memset(d,0x3f,sizeof(d));
    dij();

    ull sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(d[i][j]<0x3f3f3f3f && g[i][j]!='#')sum+=(ull)d[i][j]*d[i][j];
        }
    }
    cout<<sum;
    // system("pause");
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 38824kb

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 275ms
memory: 56396kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 349ms
memory: 55796kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 20ms
memory: 47660kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 7ms
memory: 47808kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 251ms
memory: 56084kb

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:

49803413395702

result:

wrong answer 1st lines differ - expected: '49803365625286', found: '49803413395702'