oj.uz

Submission #1114479

# Submission time Handle Problem Language Result Execution time Memory
1114479 2024-11-19T02:42:34 Z adaawf Cyberland (APIO23_cyberland) C++17
100 / 100
 1786 ms 164348 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
vector<pair<int, int>> g[100005];
double f[100005][95], d[100005][95];
int dd[100005];
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
    vector<int> v, vv;
    for (int i = 0; i < n; i++) g[i].clear();
    k = min(k, 90);
    for (int i = 0; i < n; i++) {
        dd[i] = 0;
        for (int j = 0; j <= k; j++) {
            f[i][j] = d[i][j] = 1e18;
        }
    }
    for (int i = 0; i < m; i++) {
        g[x[i]].push_back({y[i], c[i]});
        g[y[i]].push_back({x[i], c[i]});
    }
    queue<int> q;
    q.push(0);
    dd[0] = 1;
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (p == h) continue;
        if (a[p] == 0) v.push_back(p);
        if (a[p] == 2) vv.push_back(p);
        for (auto w : g[p]) {
            if (dd[w.first] == 0) {
                dd[w.first] = 1;
                q.push(w.first);
            }
        }
    }
    if (dd[h] == 0) return -1;
    for (int w : v) f[w][0] = 0;
    f[0][0] = 0;
    for (int i = 0; i <= k; i++) {
        priority_queue<pair<double, int>> q;
        if (i != 0) {
            for (int j = 0; j < n; j++) {
                for (auto w : g[j]) {
                    if (w.first == h) continue;
                    f[j][i] = min(d[w.first][i] + w.second, f[j][i]);
                }
                //cout << j << " " << i << " " << f[j][i] << " " << d[2][1] << " " << n << '\n';
            }
        }
        for (int j = 0; j < n; j++) {
            if (j != h) {
                q.push({-f[j][i], j});
            }
        }
        while (!q.empty()) {
            double x = -q.top().first;
            int u = q.top().second;
            q.pop();
            if (f[u][i] != x || u == h) continue;
            for (auto w : g[u]) {
                if (f[w.first][i] > f[u][i] + w.second) {
                    f[w.first][i] = f[u][i] + w.second;
                    q.push({-f[w.first][i], w.first});
                }
            }
        }
        if (i == k) break;
        for (int j = 0; j < n; j++) {
            if (f[j][i] > 1e17) continue;
            if (a[j] <= 1) d[j][i + 1] = f[j][i];
            else if (a[j] == 2) d[j][i + 1] = f[j][i] / 2;
        }
    }
    double res = 1e18;
    for (int j = 0; j <= k; j++) {
        res = min(res, f[h][j]);
    }
    if (res > 1e17) return -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8272 KB Correct.
2 Correct 22 ms 8264 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 8264 KB Correct.
2 Correct 181 ms 8272 KB Correct.
3 Correct 177 ms 8264 KB Correct.
4 Correct 177 ms 8252 KB Correct.
5 Correct 180 ms 8272 KB Correct.
6 Correct 208 ms 21580 KB Correct.
7 Correct 271 ms 21548 KB Correct.
8 Correct 129 ms 39088 KB Correct.
9 Correct 105 ms 8164 KB Correct.
10 Correct 105 ms 8016 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 8220 KB Correct.
2 Correct 187 ms 8236 KB Correct.
3 Correct 169 ms 8264 KB Correct.
4 Correct 123 ms 8184 KB Correct.
5 Correct 115 ms 8016 KB Correct.
6 Correct 52 ms 21368 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 100108 KB Correct.
2 Correct 174 ms 8264 KB Correct.
3 Correct 151 ms 8264 KB Correct.
4 Correct 159 ms 8188 KB Correct.
5 Correct 95 ms 8184 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8528 KB Correct.
2 Correct 85 ms 8272 KB Correct.
3 Correct 93 ms 8272 KB Correct.
4 Correct 152 ms 21572 KB Correct.
5 Correct 51 ms 8016 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 8224 KB Correct.
2 Correct 71 ms 8284 KB Correct.
3 Correct 46 ms 124232 KB Correct.
4 Correct 77 ms 17252 KB Correct.
5 Correct 59 ms 8164 KB Correct.
6 Correct 87 ms 8440 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 8264 KB Correct.
2 Correct 15 ms 8272 KB Correct.
3 Correct 756 ms 157828 KB Correct.
4 Correct 477 ms 41448 KB Correct.
5 Correct 328 ms 65872 KB Correct.
6 Correct 110 ms 27096 KB Correct.
7 Correct 431 ms 43604 KB Correct.
8 Correct 319 ms 12656 KB Correct.
9 Correct 80 ms 8272 KB Correct.
10 Correct 80 ms 8272 KB Correct.
11 Correct 275 ms 8488 KB Correct.
12 Correct 95 ms 8268 KB Correct.
13 Correct 89 ms 8272 KB Correct.
14 Correct 343 ms 80984 KB Correct.
15 Correct 358 ms 25932 KB Correct.
16 Correct 77 ms 8264 KB Correct.
17 Correct 109 ms 8276 KB Correct.
18 Correct 92 ms 8232 KB Correct.
19 Correct 299 ms 8272 KB Correct.
20 Correct 7 ms 8184 KB Correct.
21 Correct 8 ms 8016 KB Correct.
22 Correct 11 ms 8528 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 8752 KB Correct.
2 Correct 30 ms 8476 KB Correct.
3 Correct 1786 ms 164348 KB Correct.
4 Correct 493 ms 19276 KB Correct.
5 Correct 840 ms 67660 KB Correct.
6 Correct 260 ms 28632 KB Correct.
7 Correct 741 ms 66172 KB Correct.
8 Correct 441 ms 10248 KB Correct.
9 Correct 167 ms 9288 KB Correct.
10 Correct 165 ms 9036 KB Correct.
11 Correct 163 ms 9288 KB Correct.
12 Correct 225 ms 9288 KB Correct.
13 Correct 191 ms 9292 KB Correct.
14 Correct 1451 ms 70636 KB Correct.
15 Correct 1752 ms 87352 KB Correct.
16 Correct 763 ms 36564 KB Correct.
17 Correct 490 ms 14612 KB Correct.
18 Correct 172 ms 9364 KB Correct.
19 Correct 244 ms 9416 KB Correct.
20 Correct 188 ms 9288 KB Correct.
21 Correct 700 ms 10304 KB Correct.
22 Correct 11 ms 8016 KB Correct.
23 Correct 14 ms 8272 KB Correct.
24 Correct 19 ms 8784 KB Correct.