QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #226842 | #5153. Delft Distance | Fyind# | RE | 2ms | 5524kb | C++23 | 2.5kb | 2023-10-26 17:09:45 | 2023-10-26 17:09:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define _ <<" "<<
#define sz(x) ((int) (x).size())
typedef pair<int, int> pii;
typedef long double ll;
const int maxn = 5e5 + 5;
struct Dijkstra {
int n;
vector<vector<pair<int, ll>>> G;
vector<ll> d;
Dijkstra(int n) : n(n+1), G(n+1) {}
void addedge(int x, int y, ll val) { G[x].push_back({y, val}); G[y].push_back({x, val}); }
void calc(int s) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
vector<bool> done(n+1);
d.assign(n+1, 1e18); d[s] = 0;
Q.push({d[s], s});
while(!Q.empty()) {
int x = Q.top().second; Q.pop();
if (done[x]) continue; else done[x] = true;
for (auto [v, len] : G[x]) if (d[v] > d[x] + len) {
d[v] = d[x] + len;
Q.push({d[v], v});
}
}
}
};
int n, m;
int getid(int x,int y) {
return x*(2*m+1) + y;
}
char A[710][710];
Dijkstra dij(getid(1500,1500)*10);
const long double lenc = acos((ll)-1)*5/2;
void add(int x4,int y4, char c) {
x4 *= 2, y4 *= 2;
int x1 = x4-2,y1 = y4-2;
int x2 = x4-2, y2 = y4;
int x3 = x4, y3 = y4-2;
int x12 = (x1+x2)/2, y12 = (y1+y2)/2;
int x13 = (x1+x3)/2, y13 = (y1+y3)/2;
int x34 = (x3+x4)/2, y34 = (y3+y4)/2;
int x24 = (x2+x4)/2, y24 = (y2+y4)/2;
dij.addedge(getid(x1,y1),getid(x12,y12), 5);
dij.addedge(getid(x12,y12),getid(x2,y2), 5);
dij.addedge(getid(x1,y1),getid(x13,y13), 5);
dij.addedge(getid(x13,y13),getid(x3,y3), 5);
dij.addedge(getid(x3,y3),getid(x34,y34), 5);
dij.addedge(getid(x34,y34),getid(x4,y4), 5);
dij.addedge(getid(x2,y2),getid(x24,y24), 5);
dij.addedge(getid(x24,y24),getid(x4,y4), 5);
if (c == 'O') {
dij.addedge(getid(x13,y13),getid(x12,y12), lenc);
dij.addedge(getid(x13,y13),getid(x34,y34), lenc);
dij.addedge(getid(x34,y34),getid(x24,y24), lenc);
dij.addedge(getid(x12,y12),getid(x24,y24), lenc);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n; ++i) {
for (int j = 1;j <= m; ++j) {
cin >> A[i][j];
}
}
for (int i = 1;i <= n; ++i) {
for (int j = 1;j <= m; ++j) {
add(i,j,A[i][j]);
}
}
dij.calc(getid(0,0));
cout << fixed << setprecision(6) << dij.d[getid(n*2,m*2)] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4492kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.415927
result:
ok found '71.4159270', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4352kb
input:
1 4 XOOX
output:
45.707963
result:
ok found '45.7079630', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4416kb
input:
1 1 X
output:
20.000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4416kb
input:
1 1 O
output:
17.853982
result:
ok found '17.8539820', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4428kb
input:
1 3 XOO
output:
35.707963
result:
ok found '35.7079630', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4360kb
input:
1 5 OXOOO
output:
55.707963
result:
ok found '55.7079630', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4484kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.831853
result:
ok found '142.8318530', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4364kb
input:
1 2 XX
output:
30.000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4340kb
input:
10 1 X X X O O O X O O X
output:
105.707963
result:
ok found '105.7079630', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4484kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.247780
result:
ok found '214.2477800', expected '214.2477796', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4604kb
input:
40 9 OOOOXOXXX XOXXXOXXO OXOXXXXXO OXOXXXOXX XXXXOXOXX XXOOXOXXX XOOXOXXXX XOXXOOXOX OXXOOOOXX XXOOOXXOO OXOOXOXXX OOOOOXOOO OXXXXXXXO OOOOOOOXX OOOXXXOOX OXOXXOOOO OOOOXOXOO OXOXOOOXO OXXOOXXXO OXOOXOOXO XXXOXOXOO XXOOOXOOX OOXXOOXOO XOOXXXXOX OXXXXOOOO OXOOOOXOX XXOXXXOOO OOXOOOXXX OXOOOOXOO OXOOO...
output:
453.517688
result:
ok found '453.5176880', expected '453.5176878', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 5524kb
input:
41 50 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...
output:
873.517688
result:
ok found '873.5176880', expected '873.5176878', error '0.0000000'
Test #13:
score: -100
Runtime Error
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...