oj.uz

Submission #1114321

# Submission time Handle Problem Language Result Execution time Memory
1114321 2024-11-18T14:19:42 Z adaawf Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 67564 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] = 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);
        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;
            //cout << u << " " << i << " " << x << " " << f[u][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 (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 25 ms 8528 KB Correct.
2 Correct 24 ms 8528 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 8528 KB Correct.
2 Correct 192 ms 8776 KB Correct.
3 Correct 185 ms 8948 KB Correct.
4 Correct 188 ms 8680 KB Correct.
5 Correct 194 ms 8528 KB Correct.
6 Correct 221 ms 13816 KB Correct.
7 Correct 299 ms 13804 KB Correct.
8 Correct 143 ms 21080 KB Correct.
9 Correct 106 ms 8528 KB Correct.
10 Correct 106 ms 8612 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 8928 KB Correct.
2 Correct 185 ms 8684 KB Correct.
3 Correct 172 ms 8852 KB Correct.
4 Correct 118 ms 8616 KB Correct.
5 Correct 125 ms 8604 KB Correct.
6 Correct 51 ms 13536 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 43328 KB Correct.
2 Correct 179 ms 8700 KB Correct.
3 Correct 155 ms 9572 KB Correct.
4 Correct 158 ms 9540 KB Correct.
5 Correct 97 ms 9468 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8776 KB Correct.
2 Correct 87 ms 8528 KB Correct.
3 Correct 91 ms 8776 KB Correct.
4 Correct 143 ms 13752 KB Correct.
5 Correct 51 ms 8528 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 8776 KB Correct.
2 Correct 73 ms 8716 KB Correct.
3 Correct 46 ms 52296 KB Correct.
4 Correct 79 ms 13600 KB Correct.
5 Correct 60 ms 8528 KB Correct.
6 Correct 86 ms 8704 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 8528 KB Correct.
2 Correct 16 ms 8784 KB Correct.
3 Correct 947 ms 67564 KB Correct.
4 Correct 457 ms 21424 KB Correct.
5 Correct 327 ms 31796 KB Correct.
6 Correct 119 ms 17256 KB Correct.
7 Correct 408 ms 23496 KB Correct.
8 Correct 314 ms 9032 KB Correct.
9 Correct 80 ms 8776 KB Correct.
10 Correct 74 ms 8748 KB Correct.
11 Correct 267 ms 8924 KB Correct.
12 Correct 95 ms 8704 KB Correct.
13 Correct 86 ms 8776 KB Correct.
14 Correct 346 ms 38360 KB Correct.
15 Correct 351 ms 16136 KB Correct.
16 Correct 77 ms 8776 KB Correct.
17 Correct 109 ms 8776 KB Correct.
18 Correct 91 ms 8776 KB Correct.
19 Correct 303 ms 8716 KB Correct.
20 Correct 7 ms 8528 KB Correct.
21 Correct 8 ms 8696 KB Correct.
22 Correct 10 ms 8892 KB Correct.

Subtask #8
0.0 / 3.0

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