QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201480#5153. Delft DistanceVengeful_Spirit#WA 17ms97636kbC++141.9kb2023-10-05 14:39:362023-10-05 14:39:37

Judging History

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

  • [2023-10-05 14:39:37]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:97636kb
  • [2023-10-05 14:39:36]
  • 提交

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'