oj.uz

Submission #985040

# Submission time Handle Problem Language Result Execution time Memory
985040 2024-05-17T09:54:42 Z thinknoexit Cyberland (APIO23_cyberland) C++17
97 / 100
 435 ms 54876 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct A {
    int v, st;
    double w;
    bool operator < (const A& o) const {
        return w > o.w;
    }
};
vector<A> adj[100100];
priority_queue<A> pq;
double dis[31][100100];
double val[31];
bool vis[100100];
int n, m, k, e;
void dfs(int v) {
    vis[v] = 1;
    if (v == e) return;
    for (auto& x : adj[v]) {
        if (!vis[x.v]) dfs(x.v);
    }
}
double solve(int NN, int M, int K, int H, vector<int> X, vector<int> Y, vector <int> C, vector<int> a) {
    n = NN, m = M, k = K, e = H;
    for (int i = 0;i < m;i++) {
        adj[X[i]].push_back({ Y[i], 0, (double)C[i] });
        adj[Y[i]].push_back({ X[i], 0, (double)C[i] });
    }
    memset(vis, 0, sizeof vis);
    dfs(0);
    if (!vis[e]) {
        for (int i = 0;i < n;i++) adj[i].clear();
        return -1;
    }
    val[0] = 1;
    for (int i = 1;i <= k;i++) val[i] = val[i - 1] * 2;
    for (int i = 0;i <= k;i++) {
        for (int j = 0;j < n;j++) dis[i][j] = 1e300;
    }
    for (int i = 0;i < n;i++) {
        if (i != 0 && a[i] != 0) continue;
        if (!vis[i]) continue;
        pq.push({ i, 0, 0 });
        dis[0][i] = 0;
    }
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        int v = x.v, st = x.st;
        if (x.w > dis[st][v]) continue;
        if (v == e) continue;
        for (auto& x : adj[v]) {
            if (dis[st][x.v] > dis[st][v] + x.w * val[st]) {
                dis[st][x.v] = dis[st][v] + x.w * val[st];
                pq.push({ x.v, st, dis[st][x.v] });
            }
            if (a[x.v] == 2 && st < k) {
                if (dis[st + 1][x.v] > dis[st][v] + x.w * val[st]) {
                    dis[st + 1][x.v] = dis[st][v] + x.w * val[st];
                    pq.push({ x.v, st + 1, dis[st + 1][x.v] });
                }
            }
        }
    }
    for (int i = 0;i < n;i++) {
        adj[i].clear();
    }
    double mn = 1e300;
    for (int j = 0;j <= k;j++) {
        if (dis[j][e] == 1e300) continue;
        mn = min(mn, dis[j][e] / val[j]);
    }
    return mn;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 27228 KB Correct.
2 Correct 28 ms 27480 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27228 KB Correct.
2 Correct 24 ms 27312 KB Correct.
3 Correct 23 ms 27224 KB Correct.
4 Correct 24 ms 27228 KB Correct.
5 Correct 26 ms 27728 KB Correct.
6 Correct 25 ms 27996 KB Correct.
7 Correct 26 ms 27996 KB Correct.
8 Correct 15 ms 28764 KB Correct.
9 Correct 24 ms 27180 KB Correct.
10 Correct 24 ms 26972 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27224 KB Correct.
2 Correct 24 ms 27996 KB Correct.
3 Correct 25 ms 27868 KB Correct.
4 Correct 27 ms 27800 KB Correct.
5 Correct 25 ms 27740 KB Correct.
6 Correct 11 ms 27996 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 32532 KB Correct.
2 Correct 102 ms 28060 KB Correct.
3 Correct 89 ms 27996 KB Correct.
4 Correct 95 ms 27984 KB Correct.
5 Correct 73 ms 27732 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27224 KB Correct.
2 Correct 26 ms 27376 KB Correct.
3 Correct 22 ms 27224 KB Correct.
4 Correct 23 ms 28508 KB Correct.
5 Correct 21 ms 26972 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27228 KB Correct.
2 Correct 21 ms 28020 KB Correct.
3 Correct 35 ms 12116 KB Correct.
4 Correct 17 ms 28708 KB Correct.
5 Correct 23 ms 27876 KB Correct.
6 Correct 26 ms 27996 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 27376 KB Correct.
2 Correct 21 ms 27576 KB Correct.
3 Correct 363 ms 29012 KB Correct.
4 Correct 213 ms 28652 KB Correct.
5 Correct 435 ms 37336 KB Correct.
6 Correct 224 ms 36300 KB Correct.
7 Correct 207 ms 30544 KB Correct.
8 Correct 186 ms 28876 KB Correct.
9 Correct 89 ms 28128 KB Correct.
10 Correct 81 ms 28140 KB Correct.
11 Correct 187 ms 28592 KB Correct.
12 Correct 95 ms 27988 KB Correct.
13 Correct 97 ms 28132 KB Correct.
14 Correct 185 ms 32500 KB Correct.
15 Correct 189 ms 29776 KB Correct.
16 Correct 91 ms 28368 KB Correct.
17 Correct 106 ms 28008 KB Correct.
18 Correct 95 ms 28172 KB Correct.
19 Correct 224 ms 28428 KB Correct.
20 Correct 11 ms 27228 KB Correct.
21 Correct 10 ms 27288 KB Correct.
22 Correct 19 ms 28252 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 54876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -