oj.uz

Submission #985236

# Submission time Handle Problem Language Result Execution time Memory
985236 2024-05-17T13:36:19 Z thinknoexit Cyberland (APIO23_cyberland) C++17
97 / 100
 417 ms 66316 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, 64);
    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 28 ms 28752 KB Correct.
2 Correct 28 ms 28764 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28764 KB Correct.
2 Correct 23 ms 28808 KB Correct.
3 Correct 24 ms 28764 KB Correct.
4 Correct 25 ms 28764 KB Correct.
5 Correct 23 ms 28764 KB Correct.
6 Correct 25 ms 29540 KB Correct.
7 Correct 26 ms 29532 KB Correct.
8 Correct 14 ms 30300 KB Correct.
9 Correct 23 ms 28672 KB Correct.
10 Correct 23 ms 28504 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28768 KB Correct.
2 Correct 23 ms 28764 KB Correct.
3 Correct 25 ms 28764 KB Correct.
4 Correct 24 ms 28508 KB Correct.
5 Correct 24 ms 28672 KB Correct.
6 Correct 9 ms 29276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 34040 KB Correct.
2 Correct 98 ms 28768 KB Correct.
3 Correct 90 ms 29004 KB Correct.
4 Correct 94 ms 28732 KB Correct.
5 Correct 73 ms 28648 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28908 KB Correct.
2 Correct 22 ms 28764 KB Correct.
3 Correct 21 ms 29016 KB Correct.
4 Correct 22 ms 29964 KB Correct.
5 Correct 21 ms 28508 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28848 KB Correct.
2 Correct 19 ms 28884 KB Correct.
3 Correct 32 ms 10344 KB Correct.
4 Correct 19 ms 29784 KB Correct.
5 Correct 22 ms 28672 KB Correct.
6 Correct 21 ms 28760 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 28844 KB Correct.
2 Correct 20 ms 28932 KB Correct.
3 Correct 328 ms 27112 KB Correct.
4 Correct 208 ms 26628 KB Correct.
5 Correct 417 ms 37576 KB Correct.
6 Correct 223 ms 36668 KB Correct.
7 Correct 205 ms 28808 KB Correct.
8 Correct 190 ms 29120 KB Correct.
9 Correct 85 ms 28900 KB Correct.
10 Correct 77 ms 28760 KB Correct.
11 Correct 182 ms 29004 KB Correct.
12 Correct 93 ms 28760 KB Correct.
13 Correct 96 ms 28764 KB Correct.
14 Correct 182 ms 30656 KB Correct.
15 Correct 193 ms 30132 KB Correct.
16 Correct 88 ms 28764 KB Correct.
17 Correct 104 ms 28780 KB Correct.
18 Correct 94 ms 28764 KB Correct.
19 Correct 224 ms 29012 KB Correct.
20 Correct 10 ms 28508 KB Correct.
21 Correct 10 ms 28508 KB Correct.
22 Correct 18 ms 29532 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 55388 KB Correct.
2 Correct 37 ms 55384 KB Correct.
3 Incorrect 267 ms 66316 KB Wrong Answer.
4 Halted 0 ms 0 KB -