oj.uz

Submission #985235

# Submission time Handle Problem Language Result Execution time Memory
985235 2024-05-17T13:34:31 Z thinknoexit Cyberland (APIO23_cyberland) C++17
100 / 100
 1281 ms 95508 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[101][100100];
double val[101];
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;
    k = min(k, 100);
    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 29 ms 29012 KB Correct.
2 Correct 32 ms 29044 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29528 KB Correct.
2 Correct 24 ms 29788 KB Correct.
3 Correct 23 ms 29788 KB Correct.
4 Correct 25 ms 29784 KB Correct.
5 Correct 23 ms 29788 KB Correct.
6 Correct 21 ms 30300 KB Correct.
7 Correct 26 ms 30728 KB Correct.
8 Correct 15 ms 30812 KB Correct.
9 Correct 23 ms 29532 KB Correct.
10 Correct 23 ms 29528 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29788 KB Correct.
2 Correct 23 ms 29532 KB Correct.
3 Correct 22 ms 29112 KB Correct.
4 Correct 24 ms 29524 KB Correct.
5 Correct 24 ms 29528 KB Correct.
6 Correct 8 ms 29528 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 34260 KB Correct.
2 Correct 99 ms 29804 KB Correct.
3 Correct 88 ms 29732 KB Correct.
4 Correct 94 ms 29520 KB Correct.
5 Correct 72 ms 29536 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29776 KB Correct.
2 Correct 23 ms 29784 KB Correct.
3 Correct 22 ms 29784 KB Correct.
4 Correct 22 ms 31068 KB Correct.
5 Correct 25 ms 29532 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29784 KB Correct.
2 Correct 19 ms 30048 KB Correct.
3 Correct 33 ms 12272 KB Correct.
4 Correct 16 ms 30300 KB Correct.
5 Correct 23 ms 29548 KB Correct.
6 Correct 21 ms 29784 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 30020 KB Correct.
2 Correct 22 ms 29016 KB Correct.
3 Correct 312 ms 29252 KB Correct.
4 Correct 208 ms 29016 KB Correct.
5 Correct 408 ms 39484 KB Correct.
6 Correct 212 ms 38356 KB Correct.
7 Correct 212 ms 30936 KB Correct.
8 Correct 187 ms 31060 KB Correct.
9 Correct 85 ms 29804 KB Correct.
10 Correct 77 ms 29776 KB Correct.
11 Correct 183 ms 30800 KB Correct.
12 Correct 98 ms 29916 KB Correct.
13 Correct 95 ms 29776 KB Correct.
14 Correct 191 ms 32752 KB Correct.
15 Correct 188 ms 32044 KB Correct.
16 Correct 89 ms 29780 KB Correct.
17 Correct 106 ms 29776 KB Correct.
18 Correct 98 ms 29776 KB Correct.
19 Correct 223 ms 30824 KB Correct.
20 Correct 10 ms 28504 KB Correct.
21 Correct 12 ms 28732 KB Correct.
22 Correct 20 ms 29784 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 83500 KB Correct.
2 Correct 60 ms 82268 KB Correct.
3 Correct 410 ms 95508 KB Correct.
4 Correct 281 ms 84912 KB Correct.
5 Correct 1281 ms 92928 KB Correct.
6 Correct 628 ms 91844 KB Correct.
7 Correct 479 ms 88628 KB Correct.
8 Correct 342 ms 84124 KB Correct.
9 Correct 243 ms 83032 KB Correct.
10 Correct 210 ms 83028 KB Correct.
11 Correct 203 ms 83280 KB Correct.
12 Correct 262 ms 83284 KB Correct.
13 Correct 268 ms 83028 KB Correct.
14 Correct 1101 ms 90392 KB Correct.
15 Correct 914 ms 88388 KB Correct.
16 Correct 362 ms 86128 KB Correct.
17 Correct 334 ms 84208 KB Correct.
18 Correct 245 ms 83284 KB Correct.
19 Correct 296 ms 83284 KB Correct.
20 Correct 264 ms 83284 KB Correct.
21 Correct 650 ms 84052 KB Correct.
22 Correct 24 ms 82264 KB Correct.
23 Correct 26 ms 82120 KB Correct.
24 Correct 50 ms 83036 KB Correct.