QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669590#8236. Snake Movefrankly6#TL 1ms7888kbC++171.8kb2024-10-23 19:06:492024-10-23 19:06:49

Judging History

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

  • [2024-10-23 19:06:49]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:7888kb
  • [2024-10-23 19:06:49]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> PII;
const int MX=3030;
const int NX=100010;
const int inf=0x3fffffff;

int N, M, K;
int mp[MX][MX], ans[MX][MX];
bool vis[MX][MX];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
queue<PII> q;
void bfs()
{
    while(!q.empty())
    {
        auto [x,y]=q.front(); q.pop();
        for(int i=1;i<=4;i++)
        {
            int nx=x+dx[i], ny=y+dy[i];
            if(mp[nx][ny]==-1) continue;
            if(nx<=0||nx>N||ny<=0||ny>M) continue;
            int upd=max(ans[x][y]+1,(mp[nx][ny]!=0)*(K-mp[nx][ny]+1));
            if(ans[nx][ny]<upd) continue;
            ans[nx][ny]=upd;
            q.push({nx,ny});
        }
    }
}
int main()
{
    // freopen("testdata.in","r",stdin);
    N=read(); M=read(); K=read();
    for(int i=1;i<=K;i++)
    {
        int x=read(), y=read();
        mp[x][y]=i;
        if(i==1)
        {
            q.push({x,y});
            vis[x][y]=1;
        }
    }
    for(int i=1;i<=N;i++)
    {
        string s; cin >> s; s=" "+s;
        for(int j=1;j<=M;j++)
        {
            if(s[j]=='#') mp[i][j]=-1;
            if(!vis[i][j]) ans[i][j]=inf;
        }
    }
    bfs();    
    ull sum=0;
    for(int i=1;i<=N;i++)
    {
        // cout << "i=" << i << '\n';
        for(int j=1;j<=M;j++)
        {
            // cout << ans[i][j] << " ";
            if(ans[i][j]!=inf) sum+=ans[i][j]*ans[i][j];
        }
        // cout << '\n';
    }
    cout << sum << '\n';
    return (0-0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

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

output:


result: