QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#502822 | #5153. Delft Distance | zhangas | WA | 8ms | 70580kb | C++14 | 2.8kb | 2024-08-03 14:48:24 | 2024-08-03 14:48:25 |
Judging History
answer
#include <bits/stdc++.h>
#define PI acos(-1)
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define PII pair<int, int>
//#define int long long
using namespace std;
const int N = 2e6 + 5;
int n, m;
int id(int x, int y)
{
return (x - 1) * (2 * m + 1) + y;
}
int hashed(int x, int y, int f)
{
if (f == 1)
{
return id((x - 1) * 2 + 1, y * 2);
}
else if (f == 2)
{
return id(x * 2 + 1, y * 2);
}
else if (f == 3)
{
return id(x * 2, (y - 1) * 2 + 1);
}
return id(x * 2, y * 2 + 1);
}
char s[1505][1505];
vector<pair<double, int>> g[N];
void addall(int x, int y)
{
g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 1)});
g[hashed(x, y, 1)].push_back({10.0, hashed(x, y + 1, 3)});
g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 1)});
g[hashed(x, y, 2)].push_back({10.0, hashed(x + 1, y + 1, 3)});
g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 1)});
g[hashed(x, y, 3)].push_back({10.0, hashed(x + 1, y, 3)});
g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 1)});
g[hashed(x, y, 4)].push_back({10.0, hashed(x + 1, y + 1, 3)});
}
void addo(int x, int y)
{
double L = PI * 5.0 / 2.0;
g[hashed(x, y, 1)].push_back({L, hashed(x, y, 4)});
g[hashed(x, y, 3)].push_back({L, hashed(x, y, 2)});
}
int st[N];
double dist[N];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
double dijkstra()
{
for (int i = 0; i < N; ++i)
dist[i] = 2e9;
dist[hashed(1, 1, 1)] = 5.0;
dist[hashed(1, 1, 3)] = 5.0;
q.push({5.0, hashed(1, 1, 1)});
q.push({5.0, hashed(1, 1, 1)});
while (q.size())
{
pair<double, int> t = q.top();
q.pop();
double distance = t.first;
int u = t.second;
if (st[u])
continue;
st[u] = 1;
for (int i = 0; i < g[u].size(); ++i)
{
int j = g[u][i].second;
double d = g[u][i].first;
if (dist[j] > dist[u] + d)
{
dist[j] = dist[u] + d;
if (!st[j])
{
q.push({dist[j], j});
}
}
}
}
return min(dist[hashed(n, m, 2)], dist[hashed(n, m, 4)]) + 5.0;
}
void solves()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> s[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
addall(i, j);
if (s[i][j] == 'O')
addo(i, j);
}
printf("%.10lf", dijkstra());
}
signed main()
{
IOS;
int T = 1;
// cin >> T;
while (T--)
solves();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 69704kb
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: 8ms
memory: 68816kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 4ms
memory: 69056kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 4ms
memory: 68780kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 68276kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 6ms
memory: 70580kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 8ms
memory: 70504kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.8318530718
result:
ok found '142.8318531', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 8ms
memory: 70348kb
input:
1 2 XX
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 8ms
memory: 70564kb
input:
10 1 X X X O O O X O O X
output:
110.0000000000
result:
wrong answer 1st numbers differ - expected: '105.7079633', found: '110.0000000', error = '0.0406028'