Submission #15694149


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 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) 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) {
			double d=hypot(X[i]-X[cur],Y[i]-Y[cur]);
			if(mask[i]&mask[cur]) d/=V;
			if(t+d<T[i]) {
				T[i]=t+d;
				Q.push({-T[i],i});
			}
		}
	}
	_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 2298 Byte
Status
Exec Time 408 ms
Memory 19960 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:45:10: warning: unused variable ‘k’ [-Wunused-variable]
   45 |  int i,j,k,l,r,x,y,z; string s;
      |          ^
./Main.cpp:45:12: warning: unused variable ‘l’ [-Wunused-variable]
   45 |  int i,j,k,l,r,x,y,z; string s;
      |            ^
./Main.cpp:45:14: warning: unused variable ‘r’ [-Wunused-variable]
   45 |  int i,j,k,l,r,x,y,z; string s;
      |              ^
./Main.cpp:45:18: warning: unused variable ‘y’ [-Wunused-variable]
   45 |  int i,j,k,l,r,x,y,z; string s;
      |                  ^
./Main.cpp:45:20: warning: unused variable ‘z’ [-Wunused-variable]
   45 |  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:104:38: note: in expansion of macro ‘FOR’
  104 |  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 7 ms 3668 KB
00-sample-01 3 ms 3700 KB
00-sample-02 2 ms 3604 KB
00-sample-03 2 ms 3676 KB
00-sample-04 2 ms 3748 KB
10-random_large-00 357 ms 11804 KB
10-random_large-01 335 ms 11740 KB
10-random_large-02 337 ms 11796 KB
10-random_large-03 408 ms 19960 KB
10-random_large-04 341 ms 11744 KB
10-random_large-05 377 ms 11760 KB
10-random_large-06 407 ms 19928 KB
10-random_large-07 338 ms 11736 KB
10-random_large-08 405 ms 19924 KB
10-random_large-09 378 ms 19960 KB
20-random_v_small-00 329 ms 5544 KB
20-random_v_small-01 360 ms 11800 KB
20-random_v_small-02 348 ms 11728 KB
20-random_v_small-03 331 ms 7612 KB
20-random_v_small-04 329 ms 7536 KB
20-random_v_small-05 328 ms 7612 KB
20-random_v_small-06 365 ms 11736 KB
20-random_v_small-07 319 ms 5544 KB
20-random_v_small-08 387 ms 11744 KB
20-random_v_small-09 356 ms 7616 KB
30-complex_graph-00 275 ms 5516 KB