Contest Duration: ~ (local time) (90 minutes)

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];
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];
}

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;
num++;
}
}
if(j+1<N) {
auto a=hoge(i,j+1,j);
if(a.first!=1e10) {
X[num]=a.first;
Y[num]=a.second;
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(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 2020-08-05 03:04:06+0900 D - Rail Tour kmjp C++ (GCC 9.2.1) 100 2298 Byte AC 408 ms 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
 AC × 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