Submission #15694129


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,V;
double X[5050],Y[5050];
ll mask[5050];
double D[5050][5050];
double T[5050];

pair<double,double> hoge(int a,int b,int c) {
	if(a==b || a==c) return {1e10,1e10};
	double mi=1e10;
	double L=0,R=1;
	int i;
	FOR(i,100) {
		double M1=(2*L+R)/3;
		double M2=(2*R+L)/3;
		double X1=X[b]+(X[c]-X[b])*M1;
		double Y1=Y[b]+(Y[c]-Y[b])*M1;
		double X2=X[b]+(X[c]-X[b])*M2;
		double Y2=Y[b]+(Y[c]-Y[b])*M2;
		double D1=hypot(X[a]-X1,Y[a]-Y1)+hypot(X[c]-X1,Y[c]-Y1)/V;
		double D2=hypot(X[a]-X2,Y[a]-Y2)+hypot(X[c]-X2,Y[c]-Y2)/V;
		
		if(D1<=D2) R=M2;
		if(D2<=D1) L=M1;
		mi=min({mi,D1,D2});
	}
	
	return {X[b]+(X[c]-X[b])*L,Y[b]+(Y[c]-Y[b])*L};
	
}

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>V;
	cin>>X[N]>>Y[N]>>X[N+1]>>Y[N+1];
	
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		mask[i]=1LL<<i;
		if(i) mask[i]|=1LL<<(i-1);
	}
	
	int num=N+2;
	FOR(i,N+2) FOR(j,N) {
		if(j) {
			auto a=hoge(i,j-1,j);
			if(a.first!=1e10) {
				X[num]=a.first;
				Y[num]=a.second;
				mask[num]=1LL<<(j-1);
				num++;
			}
		}
		if(j+1<N) {
			auto a=hoge(i,j+1,j);
			if(a.first!=1e10) {
				X[num]=a.first;
				Y[num]=a.second;
				mask[num]=(1LL<<j);
				num++;
			}
		}
	}
	
	FOR(x,num) FOR(y,num) {
		D[x][y]=hypot(X[x]-X[y],Y[x]-Y[y]);
		if(mask[x]&mask[y]) D[x][y]/=V;
	}
	
	
	
	FOR(x,num) T[x]=1e10;
	T[N]=0;
	priority_queue<pair<double,int>> Q;
	Q.push({0,N});
	while(Q.size()) {
		double t=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(t!=T[cur]) continue;
		FOR(i,num) if(t+D[cur][i]<T[i]) {
			T[i]=t+D[cur][i];
			Q.push({-T[i],i});
		}
		
	}
	/*
	FOR(x,num) {
		_P("%d %.6lf %.6lf %lld %.12lf\n",x,X[x],Y[x],mask[x],T[x]);
	}
	*/
	_P("%.12lf\n",T[N+1]);
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

Submission Info

Submission Time
Task D - Rail Tour
User kmjp
Language C++ (GCC 9.2.1)
Score 100
Code Size 2456 Byte
Status
Exec Time 552 ms
Memory 215364 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:46:10: warning: unused variable ‘k’ [-Wunused-variable]
   46 |  int i,j,k,l,r,x,y,z; string s;
      |          ^
./Main.cpp:46:12: warning: unused variable ‘l’ [-Wunused-variable]
   46 |  int i,j,k,l,r,x,y,z; string s;
      |            ^
./Main.cpp:46:14: warning: unused variable ‘r’ [-Wunused-variable]
   46 |  int i,j,k,l,r,x,y,z; string s;
      |              ^
./Main.cpp:46:20: warning: unused variable ‘z’ [-Wunused-variable]
   46 |  int i,j,k,l,r,x,y,z; string s;
      |                    ^
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:7:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:114:38: note: in expansion of macro ‘FOR’
  114 |  FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
      |                                      ^~~

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
× 26
Set Name Test Cases
All 00-sample-00, 00-sample-01, 00-sample-02, 00-sample-03, 00-sample-04, 10-random_large-00, 10-random_large-01, 10-random_large-02, 10-random_large-03, 10-random_large-04, 10-random_large-05, 10-random_large-06, 10-random_large-07, 10-random_large-08, 10-random_large-09, 20-random_v_small-00, 20-random_v_small-01, 20-random_v_small-02, 20-random_v_small-03, 20-random_v_small-04, 20-random_v_small-05, 20-random_v_small-06, 20-random_v_small-07, 20-random_v_small-08, 20-random_v_small-09, 30-complex_graph-00
Case Name Status Exec Time Memory
00-sample-00 10 ms 3792 KB
00-sample-01 2 ms 3900 KB
00-sample-02 2 ms 3784 KB
00-sample-03 2 ms 3772 KB
00-sample-04 2 ms 3848 KB
10-random_large-00 493 ms 207200 KB
10-random_large-01 480 ms 207228 KB
10-random_large-02 474 ms 207264 KB
10-random_large-03 547 ms 215284 KB
10-random_large-04 473 ms 207236 KB
10-random_large-05 520 ms 207232 KB
10-random_large-06 552 ms 215352 KB
10-random_large-07 473 ms 207232 KB
10-random_large-08 545 ms 215364 KB
10-random_large-09 520 ms 215348 KB
20-random_v_small-00 470 ms 200976 KB
20-random_v_small-01 501 ms 207228 KB
20-random_v_small-02 485 ms 207200 KB
20-random_v_small-03 471 ms 202984 KB
20-random_v_small-04 471 ms 202972 KB
20-random_v_small-05 471 ms 202996 KB
20-random_v_small-06 512 ms 207236 KB
20-random_v_small-07 471 ms 200944 KB
20-random_v_small-08 531 ms 207156 KB
20-random_v_small-09 495 ms 202952 KB
30-complex_graph-00 400 ms 200920 KB