QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#96435 | #5153. Delft Distance | Ahmed_Abdelmegeed# | TL | 4364ms | 71732kb | C++20 | 4.9kb | 2023-04-13 21:28:26 | 2023-04-13 21:28:28 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 700 + 10, INF = 1e18;
const ld pi = acos(-1);
const int mod = 1e9 + 7, LOG = 20;
const ld eps = 1e-4;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = { -1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, x, y;
ld sidecircle = 0.5 * pi * 5;
ld dis[N][N][10], vis[N][N][10];
char grid[N][N];
void zbtsquare(int x, int y) {
ld cur;
for (int i = 0; i < 8; i++) {
cur = 0;
for (int j = i; j < i + 8; j++) {
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += 5;
}
cur = 0;
for (int j = i; j > i - 8; j--) {
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += 5;
}
}
}
void zbtcircle(int x, int y) {
ld cur;
for (int i = 1; i < 8; i += 2) {
cur = 0;
for (int j = i; j < i + 8; j += 2) {
//cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += sidecircle;
}
cur = 0;
for (int j = i; j > i - 8; j -= 2) {
//cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += sidecircle;
}
}
}
bool valid(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void trantition(int x, int y) {
dis[x + 1][y - 1][2] = min(dis[x + 1][y - 1][2], dis[x][y][6]);
dis[x][y + 1][0] = min(dis[x][y + 1][0], dis[x][y][2]);
dis[x][y + 1][7] = min(dis[x][y + 1][7], dis[x][y][3]);
dis[x][y + 1][6] = min(dis[x][y + 1][6], dis[x][y][4]);
dis[x + 1][y + 1][0] = min(dis[x + 1][y + 1][0], dis[x][y][4]);
dis[x + 1][y][2] = min(dis[x + 1][y][2], dis[x][y][4]);
dis[x + 1][y][1] = min(dis[x + 1][y][1], dis[x][y][5]);
dis[x + 1][y][0] = min(dis[x + 1][y][0], dis[x][y][6]);
dis[x - 1][y + 1][6] = min(dis[x - 1][y + 1][6], dis[x][y][2]);
dis[x][y - 1][2] = min(dis[x][y - 1][2], dis[x][y][0]);
dis[x][y - 1][3] = min(dis[x][y - 1][3], dis[x][y][7]);
dis[x][y - 1][4] = min(dis[x][y - 1][4], dis[x][y][6]);
dis[x - 1][y - 1][4] = min(dis[x - 1][y - 1][4], dis[x][y][0]);
dis[x - 1][y][6] = min(dis[x - 1][y][6], dis[x][y][0]);
dis[x - 1][y][5] = min(dis[x - 1][y][5], dis[x][y][1]);
dis[x - 1][y][4] = min(dis[x - 1][y][4], dis[x][y][2]);
}
void solve() {
priority_queue<pair<ld, pair<pair<int, int>, int>>> pq;
dis[1][1][0] = 0;
zbtsquare(1, 1);
if (grid[1][1] == 'O') {
zbtcircle(1, 1);
zbtsquare(1, 1);
}
for (int i = 0; i < 8; i++) {
pq.push({ -dis[1][1][i], {{1, 1}, i}});
vis[1][1][i] = dis[1][1][i];
}
ld cost;
int state, nx, ny;
while (pq.size()) {
x = pq.top().second.first.first;
y = pq.top().second.first.second;
cost = -pq.top().first;
state = pq.top().second.second;
pq.pop();
if (dis[x][y][state] > cost) {
continue;
}
trantition(x, y);
for (int i = 0; i < 8; i++) {
nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny)) {
zbtsquare(nx, ny);
if (grid[nx][ny] == 'O') {
zbtcircle(nx, ny);
zbtsquare(nx, ny);
}
}
for (int j = 0; j < 8; j++) {
if (vis[nx][ny][j] > dis[nx][ny][j] && valid(nx, ny)) {
vis[nx][ny][j] = dis[nx][ny][j];
pq.push({ -dis[nx][ny][j], {{nx, ny}, j}});
}
}
}
}
}
void dowork() {
cin >> n >> m;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= 8; k++) {
dis[i][j][k] = vis[i][j][k] = 2e18;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
}
}
solve();
cout << fixed << setprecision(10) << dis[n][m][4] << el;
}
signed main() {
fast
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
dowork();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 7648kb
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: 1ms
memory: 5836kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7760kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5840kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 3ms
memory: 7624kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 3ms
memory: 5672kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 5ms
memory: 7920kb
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: 0ms
memory: 7872kb
input:
1 2 XX
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7812kb
input:
10 1 X X X O O O X O O X
output:
105.7079632679
result:
ok found '105.7079633', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 6ms
memory: 9808kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.2477796077
result:
ok found '214.2477796', expected '214.2477796', error '0.0000000'
Test #11:
score: 0
Accepted
time: 19ms
memory: 16080kb
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.5176877776
result:
ok found '453.5176878', expected '453.5176878', error '0.0000000'
Test #12:
score: 0
Accepted
time: 58ms
memory: 16092kb
input:
41 50 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...
output:
873.5176877776
result:
ok found '873.5176878', expected '873.5176878', error '0.0000000'
Test #13:
score: 0
Accepted
time: 4364ms
memory: 71732kb
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
8560.0000000000
result:
ok found '8560.0000000', expected '8560.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 371ms
memory: 18656kb
input:
49 297 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
3451.4159265359
result:
ok found '3451.4159265', expected '3451.4159265', error '0.0000000'
Test #15:
score: 0
Accepted
time: 808ms
memory: 54640kb
input:
357 83 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
4342.0575041173
result:
ok found '4342.0575041', expected '4342.0575041', error '0.0000000'
Test #16:
score: -100
Time Limit Exceeded
input:
417 615 XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...