QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201480 | #5153. Delft Distance | Vengeful_Spirit# | WA | 17ms | 97636kb | C++14 | 1.9kb | 2023-10-05 14:39:36 | 2023-10-05 14:39:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, double>> G[700*700*8];
double d[700*700*8];
int h, w;
void dij() {
for(int i = 1; i <= h*(3*w+2)+2*w+1; ++i) d[i] = 700*700*10;
d[1]=0;
priority_queue<pair<double, int>> q;
q.push({0, 1});
while(!q.empty()) {
auto [dis, x] = q.top();q.pop();
if(-dis > d[x]) continue;
for(auto [y, w] : G[x]) if(d[y] > d[x] + w) {
d[y] = d[x] + w;
q.push({-d[y], y});
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w;
vector<string> s(h);
for(int i = 0; i < h; ++i) {
cin >> s[i];
}
for(int i = 0; i <= h; ++i) {
int now = i*(2*w+1+w+1);
for(int j = 1; j < 2*w+1; ++j) {
G[now+j].push_back({now+j+1, 5});
G[now+j+1].push_back({now+j, 5});
if(j%2==1) {
if(i!=h) {
G[now+j].push_back({now+2*w+1+(j+1)/2, 5});
G[now+2*w+1+(j+1)/2].push_back({now+j, 5});
} if(i!=0) {
G[now+j].push_back({now-w-1+(j+1)/2, 5});
G[now-w-1+(j+1)/2].push_back({now+j, 5});
}
}
}
}
double len = acos(-1)*2.50;
for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) if(s[i][j] == 'O') {
int _1 = i*(w*3+2)+2*j+2;
int _2 = i*(w*3+2)+(2*w+1)+j+2;
int _3 = (i+1)*(w*3+2)+2*j+2;
int _4 = i*(w*3+2)+(2*w+1)+j+1;
G[_1].push_back({_2, len});
G[_2].push_back({_1, len});
G[_3].push_back({_2, len});
G[_2].push_back({_3, len});
G[_1].push_back({_4, len});
G[_4].push_back({_1, len});
G[_3].push_back({_4, len});
G[_4].push_back({_3, len});
}
dij();
cout << fixed << setprecision(10) << d[h*(3*w+2)+2*w+1] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 96112kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.4159265359
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 7ms
memory: 97220kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 8ms
memory: 97636kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 8ms
memory: 96100kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 4ms
memory: 97300kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 17ms
memory: 96104kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: -100
Wrong Answer
time: 8ms
memory: 96180kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
144.9778714378
result:
wrong answer 1st numbers differ - expected: '142.8318531', found: '144.9778714', error = '0.0150248'