oj.uz

Submission #985237

# Submission time Handle Problem Language Result Execution time Memory
985237 2024-05-17T13:36:50 Z thinknoexit Cyberland (APIO23_cyberland) C++17
100 / 100
 1255 ms 92980 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, 96);
    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 28756 KB Correct.
2 Correct 28 ms 28712 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28776 KB Correct.
2 Correct 23 ms 28764 KB Correct.
3 Correct 28 ms 28760 KB Correct.
4 Correct 23 ms 28764 KB Correct.
5 Correct 23 ms 28764 KB Correct.
6 Correct 21 ms 29532 KB Correct.
7 Correct 26 ms 29532 KB Correct.
8 Correct 14 ms 30300 KB Correct.
9 Correct 29 ms 28504 KB Correct.
10 Correct 23 ms 28672 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28764 KB Correct.
2 Correct 27 ms 28764 KB Correct.
3 Correct 22 ms 28764 KB Correct.
4 Correct 24 ms 28508 KB Correct.
5 Correct 24 ms 28504 KB Correct.
6 Correct 8 ms 29276 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 34008 KB Correct.
2 Correct 98 ms 28760 KB Correct.
3 Correct 87 ms 28752 KB Correct.
4 Correct 94 ms 28756 KB Correct.
5 Correct 82 ms 28644 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28764 KB Correct.
2 Correct 23 ms 28760 KB Correct.
3 Correct 22 ms 28764 KB Correct.
4 Correct 22 ms 30044 KB Correct.
5 Correct 20 ms 28508 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28920 KB Correct.
2 Correct 19 ms 28764 KB Correct.
3 Correct 34 ms 10496 KB Correct.
4 Correct 16 ms 30196 KB Correct.
5 Correct 22 ms 28612 KB Correct.
6 Correct 20 ms 28764 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 28764 KB Correct.
2 Correct 20 ms 28764 KB Correct.
3 Correct 328 ms 26972 KB Correct.
4 Correct 206 ms 26580 KB Correct.
5 Correct 434 ms 37576 KB Correct.
6 Correct 220 ms 36708 KB Correct.
7 Correct 206 ms 28752 KB Correct.
8 Correct 199 ms 29008 KB Correct.
9 Correct 85 ms 28932 KB Correct.
10 Correct 80 ms 28884 KB Correct.
11 Correct 185 ms 29088 KB Correct.
12 Correct 94 ms 28760 KB Correct.
13 Correct 95 ms 29016 KB Correct.
14 Correct 191 ms 30696 KB Correct.
15 Correct 192 ms 29888 KB Correct.
16 Correct 89 ms 28760 KB Correct.
17 Correct 119 ms 28764 KB Correct.
18 Correct 94 ms 28888 KB Correct.
19 Correct 228 ms 28816 KB Correct.
20 Correct 10 ms 28760 KB Correct.
21 Correct 11 ms 28504 KB Correct.
22 Correct 18 ms 29532 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 79964 KB Correct.
2 Correct 53 ms 80220 KB Correct.
3 Correct 405 ms 92980 KB Correct.
4 Correct 277 ms 80732 KB Correct.
5 Correct 1255 ms 89028 KB Correct.
6 Correct 650 ms 88268 KB Correct.
7 Correct 492 ms 84080 KB Correct.
8 Correct 341 ms 80248 KB Correct.
9 Correct 248 ms 80384 KB Correct.
10 Correct 205 ms 80212 KB Correct.
11 Correct 209 ms 79928 KB Correct.
12 Correct 261 ms 80216 KB Correct.
13 Correct 261 ms 80224 KB Correct.
14 Correct 1071 ms 86228 KB Correct.
15 Correct 983 ms 84404 KB Correct.
16 Correct 360 ms 81912 KB Correct.
17 Correct 331 ms 80212 KB Correct.
18 Correct 251 ms 80032 KB Correct.
19 Correct 306 ms 80208 KB Correct.
20 Correct 259 ms 80064 KB Correct.
21 Correct 657 ms 80308 KB Correct.
22 Correct 23 ms 79708 KB Correct.
23 Correct 25 ms 79896 KB Correct.
24 Correct 53 ms 80988 KB Correct.