oj.uz

Submission #1114478

# Submission time Handle Problem Language Result Execution time Memory
1114478 2024-11-19T02:41:42 Z adaawf Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 160216 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();
    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;
    k = min(k, 90);
    if (k <= 90) {
        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;
    }
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:10:17: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     vector<int> v, vv;
      |                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8528 KB Correct.
2 Correct 23 ms 8528 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 9032 KB Correct.
2 Correct 187 ms 9288 KB Correct.
3 Correct 177 ms 8740 KB Correct.
4 Correct 179 ms 8264 KB Correct.
5 Correct 190 ms 9288 KB Correct.
6 Correct 219 ms 22352 KB Correct.
7 Correct 296 ms 21920 KB Correct.
8 Correct 139 ms 39528 KB Correct.
9 Correct 107 ms 8780 KB Correct.
10 Correct 109 ms 8896 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 8492 KB Correct.
2 Correct 182 ms 9248 KB Correct.
3 Correct 170 ms 9288 KB Correct.
4 Correct 117 ms 9032 KB Correct.
5 Correct 116 ms 9032 KB Correct.
6 Correct 48 ms 21464 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 101216 KB Correct.
2 Correct 171 ms 9032 KB Correct.
3 Correct 156 ms 9032 KB Correct.
4 Correct 168 ms 9104 KB Correct.
5 Correct 96 ms 8944 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 9020 KB Correct.
2 Correct 86 ms 9156 KB Correct.
3 Correct 93 ms 9300 KB Correct.
4 Correct 162 ms 22152 KB Correct.
5 Correct 53 ms 8776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 9288 KB Correct.
2 Correct 75 ms 8788 KB Correct.
3 Correct 48 ms 126024 KB Correct.
4 Correct 84 ms 17884 KB Correct.
5 Correct 61 ms 9044 KB Correct.
6 Correct 88 ms 9288 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 9032 KB Correct.
2 Correct 17 ms 8284 KB Correct.
3 Correct 780 ms 160216 KB Correct.
4 Correct 453 ms 43740 KB Correct.
5 Correct 332 ms 67636 KB Correct.
6 Correct 109 ms 28608 KB Correct.
7 Correct 419 ms 44972 KB Correct.
8 Correct 312 ms 14668 KB Correct.
9 Correct 80 ms 9204 KB Correct.
10 Correct 77 ms 9192 KB Correct.
11 Correct 271 ms 10312 KB Correct.
12 Correct 98 ms 9292 KB Correct.
13 Correct 88 ms 9112 KB Correct.
14 Correct 365 ms 82512 KB Correct.
15 Correct 364 ms 27724 KB Correct.
16 Correct 83 ms 9288 KB Correct.
17 Correct 115 ms 9288 KB Correct.
18 Correct 97 ms 9296 KB Correct.
19 Correct 306 ms 10168 KB Correct.
20 Correct 7 ms 8016 KB Correct.
21 Correct 10 ms 8272 KB Correct.
22 Correct 11 ms 8784 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 24836 KB Time limit exceeded
2 Halted 0 ms 0 KB -