oj.uz

Submission #14536

# Submission time Handle Problem Language Result Execution time Memory
14536 2015-05-19T13:55:47 Z comet 물병 (JOI14_bottle) C++
0 / 100
 5000 ms 46504 KB 
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<cstring>
using namespace std;
typedef pair<int,int> pp;

char a[2222][2222];
int y[111111],x[111111];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int H,W,P,Q;
pp d[2222][2222];
set<pp> town;
struct st{
	int M,c,xx,yy;
	st(int M_,int c_,int yy_,int xx_):M(M_),c(c_),xx(xx_),yy(yy_){}
	st(){}
};
int bfs(int S,int T){
	queue<st> Q;
	Q.push(st(0,0,y[S],x[S]));
	d[y[S]][x[S]]=pp(0,0);
	st here,next;
	int ty,tx;
	pp cost;
	bool ok;
	while(!Q.empty()){
		here=Q.front();
		Q.pop();

		for(int i=0;i<4;i++){
			ok=false;
			cost=pp(here.M,here.c+1);
			if(here.M==here.c)cost.first++;

			ty=here.yy+dy[i],tx=here.xx+dx[i];

			if(town.find(pp(ty,tx))!=town.end())ok=true;
			if(ok)cost=pp(here.M,0);

			if(a[ty][tx]=='.'&&(d[ty][tx].first<0||d[ty][tx]>cost)){
				d[ty][tx]=cost;
				if(ok){
					next=st(max(here.M,d[ty][tx].first),0,ty,tx);
					Q.push(next);
				}
				else{
					next=st(max(here.M,d[ty][tx].first),d[ty][tx].second,ty,tx);
					Q.push(next);
				}
			}
		}
	}
	/*for(int i=1;i<=H;i++,puts("")){
		for(int j=1;j<=W;j++){
			printf("%d(%d) ",d[i][j].first,d[i][j].second);
		}
	}*/
	return d[y[T]][x[T]].first;
}
int main(){
	scanf("%d%d%d%d",&H,&W,&P,&Q);
	for(int i=1;i<=H;i++)scanf("%s",&a[i][1]);
	for(int i=1;i<=P;i++){
		scanf("%d%d",&y[i],&x[i]);
		town.insert(pp(y[i],x[i]));
	}
	int S,T;
	for(int i=0;i<Q;i++){
		memset(d,-1,sizeof(d));
		scanf("%d%d",&S,&T);
		printf("%d\n",bfs(S,T));
	}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 45848 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 45976 KB Output is correct
2 Execution timed out 5000 ms 46236 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 45980 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 46504 KB Program timed out
2 Halted 0 ms 0 KB -