Submission #19364


Source Code Expand

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

typedef pair<int,int> pii;
typedef pair<double,pii> pdii;

int main(){
	int n, m;
	int s, gy, gx;
	char ch;
	cin >> n >> m;
	vector<vector<int> > c( n + 2, vector<int>( m + 2, -1 ) );
	for( int i = 1; i <= n; ++i ){
		for( int j = 1; j <= m; ++j ){
			cin >> ch;
			switch( ch ){
				case 's':
					s = i * 1024 + j;
					break;
				case 'g':
					gy = i;
					gx = j;
					c[i][j] = 1000000000;
					break;
				case '#':
					break;
				default:
					c[i][j] = ch - '0';
					break;
			}
		}
	}
	
	priority_queue<pdii> q[2];
	q[0].push( pdii( 100.0, pii(s, s) ) );
	double r = 0.99;
	double maxgl = -1.0;
	vector<vector<double> > maxl( n + 2, vector<double>( m + 2, -1.0 ) );
	vector<vector<bool> > check( n + 2, vector<bool>( m + 2 ) );

	int d[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

	int t = 1;
	int z = 0;
	while( !q[z].empty() ){
		while( !q[z].empty() ){
			pdii p = q[z].top();
			q[z].pop();
			int y = p.second.first / 1024;
			int x = p.second.first % 1024;
			
			if( !check[y][x] ){
				check[y][x] = true;
				
				for( int k = 0; k < 4; ++k ){
					int ny = y + d[k][0];
					int nx = x + d[k][1];
					int np = ny * 1024 + nx;

					if( np != p.second.second && c[ny][nx] != -1 ){
						double nl = min( r * c[ny][nx], p.first );
						if( maxgl < nl && maxl[ny][nx] < nl ){
							maxl[ny][nx] = nl;
							q[!z].push( pdii( nl, pii(ny * 1024 + nx, p.second.first) ) );
						}
					}
				}
			}
		}

		if( maxl[gy][gx] > maxgl ){
			maxgl = maxl[gy][gx];
		}
		
		for( int i = 1; i <= n; ++i ){
			for( int j = 1; j <= m; ++j ){
				check[i][j] = false;
				maxl[i][j] = -1.0;
			}
		}
		
		r *= 0.99;
		++t;
		z = !z;
	}
	
	if( maxgl < 0.0 ){
		printf("-1\n");
	}
	else{
		printf("%.15f\n", maxgl );
	}
}

Submission Info

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

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 42
TLE × 20
RE × 2
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 22 ms 780 KB
00_mini_02.txt AC 21 ms 796 KB
00_mini_03.txt AC 21 ms 816 KB
00_mini_04.txt AC 21 ms 788 KB
00_mini_05.txt AC 21 ms 792 KB
00_sample_01.txt AC 21 ms 788 KB
00_sample_02.txt AC 21 ms 784 KB
01_rnd_01.txt TLE 5030 ms 6356 KB
01_rnd_02.txt AC 328 ms 2440 KB
01_rnd_03.txt AC 46 ms 1144 KB
01_rnd_04.txt AC 169 ms 1400 KB
01_rnd_05.txt AC 40 ms 1020 KB
01_rnd_06.txt AC 26 ms 796 KB
01_rnd_07.txt AC 51 ms 1144 KB
01_rnd_08.txt AC 558 ms 3192 KB
01_rnd_09.txt AC 1215 ms 3716 KB
01_rnd_10.txt AC 2083 ms 4260 KB
01_rnd_11.txt AC 879 ms 2812 KB
01_rnd_12.txt AC 409 ms 2056 KB
01_rnd_13.txt AC 119 ms 1024 KB
01_rnd_14.txt RE 0 ms 4340 KB
01_rnd_15.txt AC 1055 ms 2820 KB
01_rnd_16.txt AC 50 ms 1412 KB
01_rnd_17.txt TLE 5030 ms 2812 KB
01_rnd_18.txt TLE 5029 ms 1020 KB
01_rnd_19.txt TLE 5029 ms 1392 KB
01_rnd_20.txt TLE 5030 ms 1016 KB
02_maxrnd_01.txt AC 1229 ms 4820 KB
02_maxrnd_02.txt AC 540 ms 4388 KB
02_maxrnd_03.txt AC 1353 ms 4884 KB
02_maxrnd_04.txt AC 2124 ms 5516 KB
02_maxrnd_05.txt AC 1446 ms 4860 KB
02_maxrnd_06.txt TLE 5031 ms 7040 KB
02_maxrnd_07.txt AC 355 ms 4348 KB
02_maxrnd_08.txt AC 229 ms 4088 KB
02_maxrnd_09.txt TLE 5031 ms 7140 KB
02_maxrnd_10.txt AC 577 ms 4472 KB
02_maxrnd_11.txt TLE 5030 ms 7020 KB
02_maxrnd_12.txt AC 2081 ms 5504 KB
02_maxrnd_13.txt AC 3308 ms 5592 KB
02_maxrnd_14.txt AC 4801 ms 6928 KB
02_maxrnd_15.txt AC 634 ms 4240 KB
02_maxrnd_16.txt AC 4526 ms 5428 KB
02_maxrnd_17.txt RE 0 ms 4892 KB
02_maxrnd_18.txt TLE 5030 ms 3964 KB
02_maxrnd_19.txt TLE 5029 ms 3968 KB
03_hard_01.txt TLE 5030 ms 6944 KB
03_hard_02.txt TLE 5030 ms 6940 KB
03_hard_03.txt TLE 5030 ms 3956 KB
03_hard_04.txt TLE 5030 ms 3964 KB
03_hard_05.txt TLE 5030 ms 6940 KB
03_hard_06.txt TLE 5030 ms 6972 KB
03_hard_07.txt TLE 5030 ms 3844 KB
03_hard_08.txt TLE 5029 ms 4088 KB
04_open_01.txt TLE 5030 ms 7060 KB
04_open_02.txt TLE 5031 ms 6956 KB
05_minihard_01.txt AC 27 ms 812 KB
05_minihard_02.txt AC 28 ms 788 KB
05_minihard_03.txt AC 22 ms 820 KB
05_minihard_04.txt AC 29 ms 792 KB
05_minihard_05.txt AC 26 ms 792 KB
05_minihard_06.txt AC 28 ms 796 KB
05_minihard_07.txt AC 22 ms 788 KB
05_minihard_08.txt AC 32 ms 756 KB