QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548142#8236. Snake MoveWhaleAtColaTL 4ms79824kbC++172.0kb2024-09-05 15:51:242024-09-05 15:51:24

Judging History

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

  • [2024-09-05 15:51:24]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:79824kb
  • [2024-09-05 15:51:24]
  • 提交

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
........................................................................................................#................................................................................................................................................................#................

output:


result: