oj.uz

Submission #755372

# Submission time Handle Problem Language Result Execution time Memory
755372 2023-06-10T02:11:11 Z IloveN Cyberland (APIO23_cyberland) C++17
100 / 100
 2015 ms 80224 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(), vr.end()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;

struct vertex {
    int v, d;
    double dist;

    bool operator < (const vertex &obj) const {
        return (d > obj.d || (d == obj.d && (dist > obj.dist || (dist == obj.dist && v > obj.v))));
    }
};

const int N = 1e5 + 10;
vector<pii> G[N];
int vis[N];
double dist[N][82];

void dfs(int u, vi& vt, int del) {
    vis[u] = 1;
    vt.eb(u);
    for (pii pa : G[u])
        if (!vis[pa.fi] && pa.fi != del) dfs(pa.fi, vt, del);
}

double solve(int n, int m, int k, int h, vi x, vi y, vi c, vi arr) {
    k = min(k, 80);
    for (int i = 0; i < n; ++i) G[i].clear();
    for (int i = 0; i < m; ++i) {
        int u = x[i], v = y[i], w = c[i];
        G[u].eb(v, w);
        G[v].eb(u, w);
    }
    for (int i = 0; i < n; ++i) vis[i] = 0;
    vi vt;
    dfs(0, vt, h);
    priority_queue<vertex> q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= k; ++j) dist[i][j] = 1e18;
    dist[0][0] = 0;
    q.push({0, 0, 0});
    for (int x : vt)
        if (!arr[x]) dist[x][0] = 0, q.push({x, 0, 0});
    while (!q.empty()) {
        int u = q.top().v, d = q.top().d;
        double w = q.top().dist;
        q.pop();
        if (w != dist[u][d] || u == h) continue;
        for (pii pa : G[u]) {
            if (dist[u][d] + pa.se < dist[pa.fi][d]) {
                dist[pa.fi][d] = dist[u][d] + pa.se;
                q.push({pa.fi, d, dist[pa.fi][d]});
            }
            if (arr[u] == 2 && d < k && dist[u][d] / 2 + pa.se < dist[pa.fi][d + 1]) {
                dist[pa.fi][d + 1] = dist[u][d] / 2 + pa.se;
                q.push({pa.fi, d + 1, dist[pa.fi][d + 1]});
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= k; ++i) res = min(res, dist[h][i]);
    if (res == 1e18) res = -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2772 KB Correct.
2 Correct 22 ms 2756 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Correct.
2 Correct 27 ms 3400 KB Correct.
3 Correct 29 ms 3412 KB Correct.
4 Correct 32 ms 3428 KB Correct.
5 Correct 26 ms 3424 KB Correct.
6 Correct 30 ms 9780 KB Correct.
7 Correct 33 ms 9560 KB Correct.
8 Correct 19 ms 16792 KB Correct.
9 Correct 32 ms 2788 KB Correct.
10 Correct 25 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3412 KB Correct.
2 Correct 29 ms 3452 KB Correct.
3 Correct 28 ms 3412 KB Correct.
4 Correct 26 ms 2792 KB Correct.
5 Correct 25 ms 2788 KB Correct.
6 Correct 12 ms 8544 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 45152 KB Correct.
2 Correct 140 ms 3484 KB Correct.
3 Correct 117 ms 3412 KB Correct.
4 Correct 133 ms 3424 KB Correct.
5 Correct 98 ms 2872 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3516 KB Correct.
2 Correct 24 ms 3516 KB Correct.
3 Correct 28 ms 3480 KB Correct.
4 Correct 29 ms 9820 KB Correct.
5 Correct 23 ms 2784 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3540 KB Correct.
2 Correct 21 ms 3536 KB Correct.
3 Correct 64 ms 56736 KB Correct.
4 Correct 19 ms 7960 KB Correct.
5 Correct 25 ms 2772 KB Correct.
6 Correct 30 ms 3540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 3428 KB Correct.
2 Correct 24 ms 3996 KB Correct.
3 Correct 651 ms 71540 KB Correct.
4 Correct 320 ms 18308 KB Correct.
5 Correct 683 ms 32832 KB Correct.
6 Correct 282 ms 15028 KB Correct.
7 Correct 389 ms 19872 KB Correct.
8 Correct 242 ms 5324 KB Correct.
9 Correct 123 ms 3468 KB Correct.
10 Correct 122 ms 3484 KB Correct.
11 Correct 235 ms 3752 KB Correct.
12 Correct 145 ms 3504 KB Correct.
13 Correct 148 ms 3564 KB Correct.
14 Correct 398 ms 36536 KB Correct.
15 Correct 293 ms 11740 KB Correct.
16 Correct 129 ms 3536 KB Correct.
17 Correct 176 ms 3472 KB Correct.
18 Correct 146 ms 3516 KB Correct.
19 Correct 379 ms 3464 KB Correct.
20 Correct 10 ms 2760 KB Correct.
21 Correct 11 ms 3332 KB Correct.
22 Correct 18 ms 3860 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 3556 KB Correct.
2 Correct 50 ms 3980 KB Correct.
3 Correct 1057 ms 80224 KB Correct.
4 Correct 383 ms 7528 KB Correct.
5 Correct 1955 ms 32840 KB Correct.
6 Correct 636 ms 15020 KB Correct.
7 Correct 672 ms 29248 KB Correct.
8 Correct 381 ms 3996 KB Correct.
9 Correct 304 ms 3532 KB Correct.
10 Correct 305 ms 3432 KB Correct.
11 Correct 154 ms 2892 KB Correct.
12 Correct 342 ms 3648 KB Correct.
13 Correct 333 ms 3680 KB Correct.
14 Correct 2015 ms 32924 KB Correct.
15 Correct 1581 ms 38372 KB Correct.
16 Correct 603 ms 15672 KB Correct.
17 Correct 405 ms 5336 KB Correct.
18 Correct 308 ms 3532 KB Correct.
19 Correct 382 ms 3548 KB Correct.
20 Correct 362 ms 3512 KB Correct.
21 Correct 1000 ms 3688 KB Correct.
22 Correct 21 ms 2644 KB Correct.
23 Correct 25 ms 3332 KB Correct.
24 Correct 39 ms 3820 KB Correct.