Submission #966392


Source Code Expand

Copy
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 10000000000000000
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
typedef pair<int,pii> pdii;
long long int MOD = 1000000007;
double power[250050];
string bd[505];
int dist[505][505];
int n,m;
int stx,sty,gx,gy;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool judge(double sc){
	priority_queue<pdii, vector<pdii>,greater<pdii> > que;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)dist[i][j]=INF;
	dist[stx][sty]=0;
	que.push( mp(0,mp(stx,sty)) );//cost,ver
	
	while(!que.empty()){
		pdii p=que.top();
		que.pop();
		
		pii v=p.second;
		if(dist[v.first][v.second]<p.first)continue;
		int x=v.first,y=v.second;
		for(int i=0;i<4;i++){
			int nx=x+dx[i];int ny=y+dy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<m){
				int d2=dist[x][y]+1;
				double hoge=bd[nx][ny]-'0';
				if(d2<dist[nx][ny]&& (bd[nx][ny]=='g'||hoge*power[d2]>sc)){
					dist[nx][ny]=d2;
					que.push(mp(d2,mp(nx,ny)));
				}
				
			}
		}
	}
	if(dist[gx][gy]!=INF)return true;
	else return false;
}
int main(){
	power[0]=1.0;
	rep(i,250000)power[i+1]=power[i]*0.99;
	
	cin >> n >> m;
	for(int i = 0 ; i < n; i++) cin >> bd[i];
	rep(i,n)rep(j,m)if(bd[i][j]=='s')stx=i,sty=j;
	rep(i,n)rep(j,m)if(bd[i][j]=='g')gx=i,gy=j;
	if(!judge(0.0)){
		cout<<"-1.0"<<endl;
		return 0;
	}
	double lo=0.0,hi=10.0;
	int ite=100;
	while(ite--){
		double md=(lo+hi)/2.0;
		if(judge(md)){
			lo = md;
		}else{
			hi = md;
		}
	}
	printf("%.9lf\n",lo);
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User Ktya_59
Language C++ (G++ 4.6.4)
Score 100
Code Size 2657 Byte
Status AC
Exec Time 2385 ms
Memory 4160 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 34 ms 2852 KB
00_mini_02.txt AC 31 ms 2800 KB
00_mini_03.txt AC 31 ms 2800 KB
00_mini_04.txt AC 31 ms 2856 KB
00_mini_05.txt AC 29 ms 2800 KB
00_sample_01.txt AC 31 ms 2840 KB
00_sample_02.txt AC 30 ms 2840 KB
01_rnd_01.txt AC 1884 ms 3952 KB
01_rnd_02.txt AC 298 ms 3636 KB
01_rnd_03.txt AC 50 ms 3056 KB
01_rnd_04.txt AC 184 ms 3228 KB
01_rnd_05.txt AC 45 ms 3056 KB
01_rnd_06.txt AC 34 ms 2992 KB
01_rnd_07.txt AC 51 ms 3696 KB
01_rnd_08.txt AC 430 ms 3824 KB
01_rnd_09.txt AC 603 ms 3880 KB
01_rnd_10.txt AC 877 ms 4016 KB
01_rnd_11.txt AC 441 ms 3488 KB
01_rnd_12.txt AC 276 ms 3368 KB
01_rnd_13.txt AC 85 ms 2968 KB
01_rnd_14.txt AC 1154 ms 3740 KB
01_rnd_15.txt AC 513 ms 3372 KB
01_rnd_16.txt AC 39 ms 3244 KB
01_rnd_17.txt AC 39 ms 3496 KB
01_rnd_18.txt AC 32 ms 2984 KB
01_rnd_19.txt AC 32 ms 3568 KB
01_rnd_20.txt AC 31 ms 3696 KB
02_maxrnd_01.txt AC 544 ms 4080 KB
02_maxrnd_02.txt AC 436 ms 4080 KB
02_maxrnd_03.txt AC 632 ms 4080 KB
02_maxrnd_04.txt AC 1232 ms 4136 KB
02_maxrnd_05.txt AC 655 ms 4080 KB
02_maxrnd_06.txt AC 2385 ms 4140 KB
02_maxrnd_07.txt AC 228 ms 4160 KB
02_maxrnd_08.txt AC 136 ms 4132 KB
02_maxrnd_09.txt AC 2382 ms 4076 KB
02_maxrnd_10.txt AC 362 ms 4080 KB
02_maxrnd_11.txt AC 2206 ms 4080 KB
02_maxrnd_12.txt AC 995 ms 4144 KB
02_maxrnd_13.txt AC 1378 ms 4080 KB
02_maxrnd_14.txt AC 1597 ms 4140 KB
02_maxrnd_15.txt AC 266 ms 4140 KB
02_maxrnd_16.txt AC 1181 ms 4136 KB
02_maxrnd_17.txt AC 909 ms 4140 KB
02_maxrnd_18.txt AC 42 ms 4136 KB
02_maxrnd_19.txt AC 41 ms 4084 KB
03_hard_01.txt AC 2076 ms 4144 KB
03_hard_02.txt AC 2150 ms 4080 KB
03_hard_03.txt AC 78 ms 4080 KB
03_hard_04.txt AC 83 ms 4132 KB
03_hard_05.txt AC 2105 ms 4144 KB
03_hard_06.txt AC 2167 ms 4080 KB
03_hard_07.txt AC 78 ms 4152 KB
03_hard_08.txt AC 85 ms 4080 KB
04_open_01.txt AC 2218 ms 4136 KB
04_open_02.txt AC 2185 ms 4080 KB
05_minihard_01.txt AC 33 ms 2856 KB
05_minihard_02.txt AC 34 ms 2856 KB
05_minihard_03.txt AC 32 ms 2928 KB
05_minihard_04.txt AC 32 ms 2852 KB
05_minihard_05.txt AC 33 ms 2928 KB
05_minihard_06.txt AC 33 ms 2856 KB
05_minihard_07.txt AC 30 ms 2928 KB
05_minihard_08.txt AC 33 ms 2864 KB