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

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

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) FOR(y,num) {
D[x][y]=hypot(X[x]-X[y],Y[x]-Y[y]);
}

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("%.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:02:19+0900 D - Rail Tour kmjp C++ (GCC 9.2.1) 100 2456 Byte AC 552 ms 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
 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 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