Submission #32989


Source Code Expand

Copy
#include <iostream>
#include <queue>
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;

#define at(a,x) (a[x/502][x%502])

char mp[502][502];
bool visit[502][502];

int df[4] = {-502, -1, 1, 502};
int s;


bool bfs( double lim ){
	fill( *visit, *visit + sizeof visit, false );

	at( visit, s ) = true;

	queue<int> q;
	q.push( s );
	q.push( -1 );
	
	double k = 0.99;

	while( q.size() > 1 ){
		int x = q.front();
		q.pop();
		
		if( x == -1 ){
			k *= 0.99;
			q.push( -1 );
		}
		else{
			for( int i = 0; i < 4; ++i ){
				int y = x + df[i];
				int c = at( mp, y );
				
				if( c == 'g' ){
					return true;
				}
				if( isdigit( c ) ){
					if( k * (c - '0') >= lim ){
						q.push( y );
					}
				}
			}
		}
	}
	
	return false;
}


int main(){
	fill( *mp, *mp + sizeof mp, '#' );

	int n, m;
	cin >> n >> m;

	for( int i = 1; i <= n; ++i ){
		cin >> &mp[i][1];
		mp[i][m + 1] = '#';
	}

	s = find( *mp, *mp + sizeof mp, 's' ) - *mp;
	
	if( !bfs( 0.0 ) ){
		puts("-1");
		return 0;
	}
	
	double left = 0.0;
	double right = 9.0;
	while( right - left > 5e-10 ){
		double mid = 0.5 * (left + right);
		if( bfs( mid ) ){
			left = mid;
		}
		else{
			right = mid;
		}
	}
	printf("%.10f\n", left );
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User climpet
Language C++ (GCC 4.4.7)
Score 0
Code Size 1317 Byte
Status TLE
Exec Time 5169 ms
Memory 1041704 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 7
TLE × 51
MLE × 6
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 32 ms 1300 KB
00_mini_02.txt AC 31 ms 1300 KB
00_mini_03.txt AC 29 ms 1296 KB
00_mini_04.txt AC 29 ms 1296 KB
00_mini_05.txt AC 22 ms 1276 KB
00_sample_01.txt AC 171 ms 1628 KB
00_sample_02.txt AC 32 ms 1280 KB
01_rnd_01.txt TLE 5160 ms 1039056 KB
01_rnd_02.txt TLE 5157 ms 1012832 KB
01_rnd_03.txt TLE 5169 ms 996956 KB
01_rnd_04.txt TLE 5149 ms 905872 KB
01_rnd_05.txt TLE 5145 ms 906152 KB
01_rnd_06.txt TLE 5132 ms 772320 KB
01_rnd_07.txt TLE 5140 ms 860984 KB
01_rnd_08.txt TLE 5143 ms 813032 KB
01_rnd_09.txt TLE 5130 ms 736096 KB
01_rnd_10.txt TLE 5135 ms 803252 KB
01_rnd_11.txt TLE 5130 ms 780868 KB
01_rnd_12.txt TLE 5118 ms 677564 KB
01_rnd_13.txt MLE 0 ms 597660 KB
01_rnd_14.txt TLE 5121 ms 685492 KB
01_rnd_15.txt MLE 0 ms 707868 KB
01_rnd_16.txt TLE 5123 ms 675872 KB
01_rnd_17.txt TLE 5119 ms 636352 KB
01_rnd_18.txt TLE 5114 ms 620680 KB
01_rnd_19.txt TLE 5120 ms 617404 KB
01_rnd_20.txt TLE 5104 ms 535260 KB
02_maxrnd_01.txt TLE 5149 ms 1041704 KB
02_maxrnd_02.txt TLE 5159 ms 1033512 KB
02_maxrnd_03.txt TLE 5160 ms 957656 KB
02_maxrnd_04.txt TLE 5146 ms 950352 KB
02_maxrnd_05.txt TLE 5146 ms 894860 KB
02_maxrnd_06.txt TLE 5142 ms 954340 KB
02_maxrnd_07.txt TLE 5136 ms 824360 KB
02_maxrnd_08.txt TLE 5141 ms 808116 KB
02_maxrnd_09.txt TLE 5130 ms 776976 KB
02_maxrnd_10.txt TLE 5127 ms 724384 KB
02_maxrnd_11.txt TLE 5137 ms 710932 KB
02_maxrnd_12.txt TLE 5134 ms 725604 KB
02_maxrnd_13.txt TLE 5126 ms 679784 KB
02_maxrnd_14.txt MLE 0 ms 685216 KB
02_maxrnd_15.txt TLE 5124 ms 662604 KB
02_maxrnd_16.txt MLE 0 ms 734112 KB
02_maxrnd_17.txt TLE 5125 ms 646152 KB
02_maxrnd_18.txt TLE 5121 ms 670260 KB
02_maxrnd_19.txt TLE 5125 ms 638580 KB
03_hard_01.txt TLE 5143 ms 932196 KB
03_hard_02.txt TLE 5141 ms 935640 KB
03_hard_03.txt TLE 5097 ms 425096 KB
03_hard_04.txt TLE 5133 ms 775388 KB
03_hard_05.txt TLE 5146 ms 928992 KB
03_hard_06.txt TLE 5146 ms 931036 KB
03_hard_07.txt TLE 5100 ms 425104 KB
03_hard_08.txt TLE 5136 ms 775892 KB
04_open_01.txt TLE 5146 ms 932704 KB
04_open_02.txt TLE 5142 ms 928280 KB
05_minihard_01.txt TLE 5142 ms 928600 KB
05_minihard_02.txt TLE 5142 ms 934364 KB
05_minihard_03.txt TLE 5097 ms 427152 KB
05_minihard_04.txt MLE 0 ms 781400 KB
05_minihard_05.txt TLE 5153 ms 930392 KB
05_minihard_06.txt MLE 0 ms 935776 KB
05_minihard_07.txt TLE 5098 ms 427536 KB
05_minihard_08.txt TLE 5133 ms 776832 KB