oj.uz

Submission #1114307

# Submission time Handle Problem Language Result Execution time Memory
1114307 2024-11-18T13:54:33 Z adaawf Cyberland (APIO23_cyberland) C++17
78 / 100
 3000 ms 69908 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
vector<pair<int, int>> g[100005];
double f[100005][35], d[100005][35];
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;
    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] = 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);
        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';
            }
        }
        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;
            //cout << u << " " << i << " " << x << " " << f[h][i] << " 328762836" << '\n';
            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 (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 8528 KB Correct.
2 Correct 24 ms 8784 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 8776 KB Correct.
2 Correct 189 ms 8692 KB Correct.
3 Correct 177 ms 8700 KB Correct.
4 Correct 183 ms 8528 KB Correct.
5 Correct 186 ms 8720 KB Correct.
6 Correct 219 ms 13836 KB Correct.
7 Correct 277 ms 13800 KB Correct.
8 Correct 134 ms 21056 KB Correct.
9 Correct 107 ms 8616 KB Correct.
10 Correct 104 ms 8612 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 8676 KB Correct.
2 Correct 185 ms 9544 KB Correct.
3 Correct 171 ms 9544 KB Correct.
4 Correct 115 ms 9492 KB Correct.
5 Correct 116 ms 9492 KB Correct.
6 Correct 53 ms 13712 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 43504 KB Correct.
2 Incorrect 228 ms 8708 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8740 KB Correct.
2 Correct 87 ms 8708 KB Correct.
3 Correct 91 ms 9000 KB Correct.
4 Correct 148 ms 13752 KB Correct.
5 Correct 53 ms 8528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 8736 KB Correct.
2 Correct 74 ms 9556 KB Correct.
3 Correct 44 ms 35152 KB Correct.
4 Correct 79 ms 12180 KB Correct.
5 Correct 61 ms 9356 KB Correct.
6 Correct 94 ms 9556 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8728 KB Correct.
2 Correct 16 ms 8784 KB Correct.
3 Correct 806 ms 69908 KB Correct.
4 Correct 474 ms 23616 KB Correct.
5 Correct 343 ms 34700 KB Correct.
6 Correct 116 ms 18652 KB Correct.
7 Correct 430 ms 22700 KB Correct.
8 Correct 317 ms 10840 KB Correct.
9 Correct 97 ms 9580 KB Correct.
10 Correct 83 ms 9544 KB Correct.
11 Correct 274 ms 10568 KB Correct.
12 Correct 100 ms 9800 KB Correct.
13 Correct 88 ms 9664 KB Correct.
14 Correct 376 ms 37616 KB Correct.
15 Correct 353 ms 18040 KB Correct.
16 Correct 79 ms 9728 KB Correct.
17 Correct 118 ms 9836 KB Correct.
18 Correct 98 ms 9740 KB Correct.
19 Correct 305 ms 10532 KB Correct.
20 Correct 8 ms 8528 KB Correct.
21 Correct 10 ms 8528 KB Correct.
22 Correct 17 ms 9040 KB Correct.

Subtask #8
0.0 / 3.0

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