Submission #19649


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

class C{
	struct Node{
		int next;
		int sec;
		double cost;
		Node(int n,int s):next(n),sec(s){}
		Node(int n,int s,double c):next(n),sec(s),cost(c){}
	};
	int N,M;
	int sy,sx,gy,gx;
	vector<string> field;
	vector<double> pre;
	bool isValid(int y,int x){
		return y>=0 && y<N && x>=0 && x<M;
	}
public:
	bool init(){
		if(scanf("%d%d",&N,&M)==EOF)return false;
		field.resize(N);
		REP(i,N){
			char buf[1024];
			scanf("%s",buf);
			field[i] = string(buf);
		}
		return true;
	}
	double check(double mid,bool isFirst=false){
		vector<vector<double> > used(N,vector<double>(M,-2));
		queue<Node> que;que.push(Node(sy*M+sx,0,100));
		while(!que.empty()){
			Node n = que.front();que.pop();
			int cy = n.next/M;
			int cx = n.next%M;
			if(cy==gy && cx==gx)return used[cy][cx];
			const int DY[] = {-1,0,1,0};
			const int DX[] = {0,1,0,-1};
			REP(i,4){
				int ny = cy+DY[i];
				int nx = cx+DX[i];
				
				if(!isValid(ny,nx) || field[ny][nx]=='#')continue;
				double cost = field[ny][nx]-'0';
				cost *= pre[n.sec+1];
				if(field[ny][nx]=='g')cost = 100;
				cost = min(n.cost,cost);
				if(cost>mid && used[ny][nx]<cost){
					if((isFirst && used[ny][nx]<0) || !isFirst){
						used[ny][nx] = cost;
						que.push(Node(ny*M+nx,n.sec+1,cost));
					}
				}
			}
		}
		return -1;
	}
	void solve(){
		REP(y,N)REP(x,M){
			if(field[y][x]=='s'){
				sy = y;
				sx = x;
			}
			if(field[y][x]=='g'){
				gy = y;
				gx = x;
			}
		}
		pre.assign(4*N*M,1);
		REP(i,4*N*M-1)pre[i+1] = pre[i]*0.99;
		vector<vector<double> > used(N,vector<double>(M,-2));
		vector<vector<int> > inQue(N,vector<int>(M,0));
		queue<Node> que;que.push(Node(sy*M+sx,0));
		inQue[sy][sx] = 1;
		used[sy][sx] = 100;
		while(!que.empty()){
			Node n = que.front();que.pop();
			int cy = n.next/M;
			int cx = n.next%M;
			//cout << cy << "," << cx << " " << used[cy][cx] << endl;
			inQue[cy][cx] = 0;
			const int DY[] = {-1,0,1,0};
			const int DX[] = {0,1,0,-1};
			REP(i,4){
				int ny = cy+DY[i];
				int nx = cx+DX[i];
				
				if(!isValid(ny,nx) || field[ny][nx]=='#')continue;
				double cost = field[ny][nx]-'0';
				cost *= pre[n.sec+1];
				if(field[ny][nx]=='g')cost = 100;
				cost = min(used[cy][cx],cost);
				if(used[ny][nx]<cost){
					used[ny][nx] = cost;
					if(!inQue[ny][nx]){
						inQue[ny][nx] = 1;
						que.push(Node(ny*M+nx,n.sec+1));
					}
				}
			}
		}
		double lb = check(0,true),ub = 10;
		if(lb>0){
			REP(i,50){
				double mid = (lb+ub)/2;
				if(check(mid)>0)lb = mid;
				else ub = mid;
			}
			printf("%.9f\n",lb);
		}
		else printf("-1\n");
		//if(used[gy][gx]<-1)printf("-1\n");
		//else printf("%.9f\n",(double)used[gy][gx]);
	}
};

int main(){
	C solver;
	while(solver.init()){
		solver.solve();
	}
	return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User nel215
Language C++ (G++ 4.6.4)
Score 0
Code Size 3289 Byte
Status TLE
Exec Time 5035 ms
Memory 14200 KB

Compile Error

./Main.cpp: In member function ‘bool C::init()’:
./Main.cpp:45:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 54
TLE × 9
RE × 1
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 788 KB
00_mini_02.txt AC 21 ms 796 KB
00_mini_03.txt AC 21 ms 792 KB
00_mini_04.txt AC 21 ms 820 KB
00_mini_05.txt AC 21 ms 792 KB
00_sample_01.txt AC 20 ms 796 KB
00_sample_02.txt AC 21 ms 760 KB
01_rnd_01.txt TLE 5030 ms 11220 KB
01_rnd_02.txt AC 953 ms 5476 KB
01_rnd_03.txt AC 67 ms 2072 KB
01_rnd_04.txt AC 477 ms 2588 KB
01_rnd_05.txt AC 59 ms 1284 KB
01_rnd_06.txt AC 26 ms 928 KB
01_rnd_07.txt AC 63 ms 2048 KB
01_rnd_08.txt AC 1489 ms 6776 KB
01_rnd_09.txt AC 2742 ms 9556 KB
01_rnd_10.txt AC 3662 ms 8488 KB
01_rnd_11.txt AC 1627 ms 6004 KB
01_rnd_12.txt AC 668 ms 4320 KB
01_rnd_13.txt AC 127 ms 1412 KB
01_rnd_14.txt AC 2471 ms 8296 KB
01_rnd_15.txt AC 839 ms 5684 KB
01_rnd_16.txt AC 74 ms 3832 KB
01_rnd_17.txt AC 67 ms 5380 KB
01_rnd_18.txt AC 24 ms 1408 KB
01_rnd_19.txt AC 33 ms 3056 KB
01_rnd_20.txt AC 23 ms 1396 KB
02_maxrnd_01.txt AC 3618 ms 13892 KB
02_maxrnd_02.txt AC 1643 ms 13864 KB
02_maxrnd_03.txt AC 4256 ms 13900 KB
02_maxrnd_04.txt TLE 5032 ms 14084 KB
02_maxrnd_05.txt AC 4088 ms 13900 KB
02_maxrnd_06.txt TLE 5031 ms 14044 KB
02_maxrnd_07.txt AC 690 ms 13844 KB
02_maxrnd_08.txt AC 456 ms 13824 KB
02_maxrnd_09.txt TLE 5031 ms 14028 KB
02_maxrnd_10.txt AC 1235 ms 13836 KB
02_maxrnd_11.txt RE 0 ms 14032 KB
02_maxrnd_12.txt AC 2904 ms 13888 KB
02_maxrnd_13.txt AC 3620 ms 13888 KB
02_maxrnd_14.txt AC 3398 ms 13860 KB
02_maxrnd_15.txt AC 534 ms 13832 KB
02_maxrnd_16.txt AC 1458 ms 13824 KB
02_maxrnd_17.txt AC 926 ms 13816 KB
02_maxrnd_18.txt AC 123 ms 13808 KB
02_maxrnd_19.txt AC 122 ms 13812 KB
03_hard_01.txt TLE 5031 ms 14152 KB
03_hard_02.txt TLE 5030 ms 14200 KB
03_hard_03.txt AC 331 ms 13824 KB
03_hard_04.txt AC 336 ms 13828 KB
03_hard_05.txt TLE 5031 ms 14088 KB
03_hard_06.txt TLE 5035 ms 14136 KB
03_hard_07.txt AC 329 ms 13820 KB
03_hard_08.txt AC 343 ms 13820 KB
04_open_01.txt AC 1268 ms 13832 KB
04_open_02.txt TLE 5031 ms 14016 KB
05_minihard_01.txt AC 33 ms 796 KB
05_minihard_02.txt AC 32 ms 792 KB
05_minihard_03.txt AC 22 ms 784 KB
05_minihard_04.txt AC 24 ms 788 KB
05_minihard_05.txt AC 32 ms 780 KB
05_minihard_06.txt AC 34 ms 772 KB
05_minihard_07.txt AC 23 ms 788 KB
05_minihard_08.txt AC 23 ms 784 KB