QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#587143	#5054. City Brain	hcywoi	WA	1113ms	101256kb	C++23	3.1kb	2024-09-24 17:46:03	2024-09-24 17:46:04

Judging History

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

[2024-09-24 17:46:04]
评测

测评结果：WA
用时：1113ms
内存：101256kb

查看

[2024-09-24 17:46:03]
提交

answer

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < m; i ++ ) {
        int u, v;
        std::cin >> u >> v;
        u --, v -- ;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int s1, t1, s2, t2;
    std::cin >> s1 >> t1 >> s2 >> t2;
    s1 --, t1 --, s2 --, t2 -- ;

    std::vector dis(n, std::vector<int>(n, 1E9));
    for (int i = 0; i < n; i ++ ) {
        std::queue<int> q;
        q.push(i);
        dis[i][i] = 0;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (auto y : adj[x]) {
                if (dis[i][y] > dis[i][x] + 1) {
                    dis[i][y] = dis[i][x] + 1;
                    q.push(y);
                }
            }
        }
    }

    long double ans;

    int d0 = dis[s1][t1], d1 = dis[s2][t2];
    if (d0 + d1 == 0) {
        ans = 0;
    } else {
        int t = k / (d0 + d1);
        int rmain = k % (d0 + d1);
        ans = 1. / (t + 1) * (d0 + d1 - rmain) + 1. / (t + 2) * rmain;
    }

    for (int s = 0; s < n; s ++ ) {
        for (int t = s + 1; t < n; t ++ ) {
            int both = dis[s][t];
            int dis1 = std::min(dis[s1][s] + dis[t][t1], dis[s1][t] + dis[s][t1]);
            int dis2 = std::min(dis[s2][s] + dis[t][t2], dis[s2][t] + dis[s][t2]);
            if (both > n || dis1 + dis2 > n) {
                continue;
            }

            auto f = [&](int x) -> long double {
                if (1LL * x * both > k) {
                    return 1E9;
                }
                int nk = k;
                long double res = 2. / (x + 1) * both;
                nk -= x * both;
                if (dis1 + dis2 > 0) {
                    int t = nk / (dis1 + dis2);
                    res += 1. / (t + 1) * (dis1 + dis2);
                    nk -= t * (dis1 + dis2);
                    if (nk > 0) {
                        if (std::min(both - 1, nk) * 2. / (x + 1) / (x + 2) > nk * 1. / (t + 1) / (t + 2)) {
                            res -= std::min(both - 1, nk) * 2. / (x + 1) / (x + 2);
                        } else {
                            res -= nk * 1. / (t + 1) / (t + 2);
                        }
                    }
                } else {
                    res -= std::min(both - 1, nk) * 2. / (x + 1) / (x + 2);
                }
                return res;
            };

            int lo = 0, hi = k;
            while (lo < hi) {
                int m = (lo + hi) / 2;
                int l = lo + m, r = hi - m;
                if (f(l) > f(r)) {
                    ans = std::min(ans, f(r));
                    lo = l + 1;
                } else {
                    ans = std::min(ans, f(l));
                    hi = r - 1;
                }
            }
            ans = std::min(ans, f(hi));
        }
    }
    std::cout << std::fixed << std::setprecision(9) << ans << "\n";

    return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3800kb

input:

output:

5.000000000

result:

ok found '5.000000000', expected '5.000000000', error '0.000000000'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3800kb

input:

1 0 100
1 1 1 1

output:

0.000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3932kb

input:

output:

0.833333333

result:

ok found '0.833333333', expected '0.833333333', error '0.000000000'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

5.000000000

result:

ok found '5.000000000', expected '5.000000000', error '0.000000000'

Test #5:

score: 0

Accepted

time: 1113ms

memory: 101256kb

input:

5000 4999 1000000000
1 2
1 3
1 4
1 5
6 2
7 3
8 4
9 5
10 6
11 7
12 8
13 9
14 10
15 11
16 12
17 13
18 14
19 15
20 16
21 17
22 18
23 19
24 20
25 21
26 22
27 23
28 24
29 25
30 26
31 27
32 28
33 29
34 30
35 31
36 32
37 33
38 34
39 35
40 36
41 37
42 38
43 39
44 40
45 41
46 42
47 43
48 44
49 45
50 46
51 47...

output:

0.024989876

result:

ok found '0.024989876', expected '0.024989876', error '0.000000000'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3860kb

input:

10 9 305097549
2 1
8 9
6 7
5 4
8 7
4 3
2 3
9 10
6 5
4 3 2 1

output:

0.000000013

result:

ok found '0.000000013', expected '0.000000013', error '0.000000000'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

3.833333333

result:

ok found '3.833333333', expected '3.833333333', error '0.000000000'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

output:

0.700000000

result:

ok found '0.700000000', expected '0.700000000', error '0.000000000'

Test #9:

score: -100

Wrong Answer

time: 1ms

memory: 3984kb

input:

output:

1.854545455

result:

wrong answer 1st numbers differ - expected: '1.8059829', found: '1.8545455', error = '0.0268898'