QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548142 | #8236. Snake Move | WhaleAtCola | TL | 4ms | 79824kb | C++17 | 2.0kb | 2024-09-05 15:51:24 | 2024-09-05 15:51:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read(){
ll x=0;bool w=0;char c=getchar();
while(c>'9'||c<'0') w|=c=='-',c=getchar();
while(c>='0'&&c<='9') x=x*10+(c-'0'),c=getchar();
return w?-x:x;
}
const int inf=0x3f3f3f3f;
inline int crd(){
char c=getchar();
while(c!='#'&&c!='.') c=getchar();
return c=='#'?inf:0;
}
const int N=3030,L=101010;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int ex[L],ey[L],g[N][N],f[N][N],qx[N*N],qy[N*N],ok[L];
inline void rmain(){
int n=read(),m=read(),l=read(),ql,qr,px,py,tx,ty,tt;
for(int i=1;i<=l;++i) ex[i]=read(),ey[i]=read();
memset(g,0x3f,sizeof g);
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) g[i][j]=crd();
for(int i=1;i<=l;++i) g[ex[i]][ey[i]]=l-i+1;
// for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) debug("%2d%c",g[i][j]," \n"[j==m]);
qx[ql=qr=1]=ex[1],qy[1]=ey[1],f[ex[1]][ey[1]]=0,tt=0;
// /*
while(ql<=qr||tt<=l){
if(ql<=qr){
px=qx[ql],py=qy[ql++],tt=f[px][py]+1;
if(tt<=l&&ok[tt]==1) qx[++qr]=ex[tt],qy[qr]=ey[tt],ok[tt]=2;
}else{
while(tt<=l&&ok[tt]!=1) ++tt;
if(tt>l) break;
px=ex[tt],py=ey[tt],ok[tt]=2;
tt=f[px][py]+1;
}
// */
/*
while(ql<=qr){
px=qx[ql],py=qy[ql++],tt=f[px][py]+1;
if(tt<=l&&ok[tt]==1) qx[++qr]=ex[tt],qy[qr]=ey[tt],ok[tt]=2;
*/
// debug("px:%d py:%d\n",px,py);
for(int k=0;k<4;++k){
tx=px+dx[k],ty=py+dy[k];
if(f[tx][ty]>tt){
if(g[tx][ty]<=tt) qx[++qr]=tx,qy[qr]=ty,f[tx][ty]=tt;
else if(g[tx][ty]!=inf) ok[l-g[tx][ty]+1]=1,f[tx][ty]=g[tx][ty];
}
}
}
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) debug("%2d%c",f[i][j]," \n"[j==m]);
ull ans=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(f[i][j]!=inf) ans+=((ull)f[i][j])*f[i][j];
printf("%llu\n",ans);
}
signed main(){
// int T=read();while(T--)
rmain();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 79584kb
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: 78340kb
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: 4ms
memory: 79824kb
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 ........................................................................................................#................................................................................................................................................................#................