QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502822#5153. Delft DistancezhangasWA 8ms70580kbC++142.8kb2024-08-03 14:48:242024-08-03 14:48:25

Judging History

你现在查看的是最新测评结果

  • [2024-08-03 14:48:25]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:70580kb
  • [2024-08-03 14:48:24]
  • 提交

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'