oj.uz

Submission #1114314

# Submission time Handle Problem Language Result Execution time Memory
1114314 2024-11-18T14:04:58 Z adaawf Cyberland (APIO23_cyberland) C++17
78 / 100
 3000 ms 124552 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
vector<pair<int, int>> g[100005];
long 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<long 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()) {
            long 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;
        }
    }
    long 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 36 ms 8016 KB Correct.
2 Correct 36 ms 8016 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 10180 KB Correct.
2 Correct 325 ms 10248 KB Correct.
3 Correct 325 ms 10184 KB Correct.
4 Correct 312 ms 10184 KB Correct.
5 Correct 325 ms 10276 KB Correct.
6 Correct 383 ms 19784 KB Correct.
7 Correct 506 ms 19796 KB Correct.
8 Correct 236 ms 33612 KB Correct.
9 Correct 203 ms 7972 KB Correct.
10 Correct 202 ms 8008 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 10076 KB Correct.
2 Correct 324 ms 10064 KB Correct.
3 Correct 306 ms 10136 KB Correct.
4 Correct 215 ms 8008 KB Correct.
5 Correct 220 ms 7980 KB Correct.
6 Correct 85 ms 17288 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1096 ms 77516 KB Correct.
2 Incorrect 389 ms 10064 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 10168 KB Correct.
2 Correct 145 ms 10064 KB Correct.
3 Correct 161 ms 10064 KB Correct.
4 Correct 256 ms 19736 KB Correct.
5 Correct 96 ms 8016 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 10064 KB Correct.
2 Correct 124 ms 10276 KB Correct.
3 Correct 50 ms 54108 KB Correct.
4 Correct 133 ms 15256 KB Correct.
5 Correct 110 ms 8008 KB Correct.
6 Correct 145 ms 10236 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 10064 KB Correct.
2 Correct 25 ms 10064 KB Correct.
3 Correct 1419 ms 124552 KB Correct.
4 Correct 792 ms 33992 KB Correct.
5 Correct 633 ms 54928 KB Correct.
6 Correct 205 ms 22888 KB Correct.
7 Correct 736 ms 38168 KB Correct.
8 Correct 533 ms 12688 KB Correct.
9 Correct 160 ms 10312 KB Correct.
10 Correct 136 ms 10064 KB Correct.
11 Correct 467 ms 10324 KB Correct.
12 Correct 181 ms 10064 KB Correct.
13 Correct 156 ms 10184 KB Correct.
14 Correct 653 ms 65028 KB Correct.
15 Correct 602 ms 24064 KB Correct.
16 Correct 143 ms 10312 KB Correct.
17 Correct 194 ms 10064 KB Correct.
18 Correct 178 ms 10064 KB Correct.
19 Correct 524 ms 10208 KB Correct.
20 Correct 11 ms 7760 KB Correct.
21 Correct 14 ms 10064 KB Correct.
22 Correct 20 ms 10576 KB Correct.

Subtask #8
0.0 / 3.0

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