oj.uz

Submission #749235

# Submission time Handle Problem Language Result Execution time Memory
749235 2023-05-27T15:03:29 Z dxz05 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 175216 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

using i128 = long double;

vector<vector<pair<int, i128>>> g;

vector<bool> used;
vector<int> zeros;
void dfs(int v, const vector<int> &arr){
    used[v] = true;
    if (arr[v] == 0 || v == 0) zeros.push_back(v);

    for (auto [u, w] : g[v]){
        if (!used[u]){
            dfs(u, arr);
        }
    }
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K = min(K, 91);

    g.clear();
    g.resize(N);

    for (int i = 0; i < M; i++) {
        if (y[i] != H) g[x[i]].emplace_back(y[i], c[i]);
        if (x[i] != H) g[y[i]].emplace_back(x[i], c[i]);
    }

    zeros.clear();
    used.assign(N, false);

    dfs(0, arr);

    const i128 INF = 2e15;

    vector<vector<i128>> dp(N, vector<i128>(K + 1, INF));
    for (int v : zeros){
        dp[v].assign(K + 1, 0);
    }

    for (int k = 0; k <= K; k++) {
        if (k > 0) {
            for (int i = 0; i < N; i++) {
                if (dp[i][k - 1] == INF) continue;
                dp[i][k] = min(dp[i][k], dp[i][k - 1]);

                if (arr[i] == 0) {
                    dp[i][k] = 0;
                }
            }
        }

        priority_queue<pair<i128, int>> pq;
        for (int i = 0; i < N; i++) {
            if (dp[i][k] != INF) pq.emplace(-dp[i][k], i);
        }

        vector<bool> processed(N, false);

        while (!pq.empty()) {
            int v = pq.top().second;
            pq.pop();
            if (processed[v]) continue;
            processed[v] = true;

            for (auto [u, w]: g[v]) {
                dp[u][k] = min(dp[u][k], dp[v][k] + w);
                if (arr[u] == 0) {
                    dp[u][k] = 0;
                }

                if (arr[u] == 2 && k < K) {
                    dp[u][k + 1] = min(dp[u][k + 1], (dp[v][k] + w) / 2);
                }

                pq.emplace(-dp[u][k], u);
            }

        }

    }

    i128 ans = INF;
    for (auto [v, w]: g[H]) {
        for (int k = 0; k <= K; k++) {
            if (dp[v][k] == INF) continue;
            if (arr[H] == 0) return 0;

            ans = min(ans, dp[v][k] + w);
            if (k < K && arr[H] == 2) {
                ans = min(ans, (dp[v][k] + w) / 2);
            }
        }
    }

    if (ans == INF) return -1;

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 356 KB Correct.
2 Correct 54 ms 440 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 1052 KB Correct.
2 Correct 738 ms 1052 KB Correct.
3 Correct 707 ms 1084 KB Correct.
4 Correct 727 ms 992 KB Correct.
5 Correct 728 ms 1060 KB Correct.
6 Correct 837 ms 7808 KB Correct.
7 Correct 1105 ms 7668 KB Correct.
8 Correct 587 ms 14996 KB Correct.
9 Correct 404 ms 556 KB Correct.
10 Correct 391 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 1212 KB Correct.
2 Correct 798 ms 1204 KB Correct.
3 Correct 683 ms 1088 KB Correct.
4 Correct 415 ms 556 KB Correct.
5 Correct 412 ms 428 KB Correct.
6 Correct 190 ms 6100 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 40560 KB Correct.
2 Correct 412 ms 1080 KB Correct.
3 Correct 381 ms 1092 KB Correct.
4 Correct 391 ms 996 KB Correct.
5 Correct 236 ms 416 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 1076 KB Correct.
2 Correct 463 ms 1100 KB Correct.
3 Correct 525 ms 1132 KB Correct.
4 Correct 672 ms 7056 KB Correct.
5 Correct 248 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 1260 KB Correct.
2 Correct 428 ms 980 KB Correct.
3 Correct 106 ms 51192 KB Correct.
4 Correct 399 ms 5164 KB Correct.
5 Correct 276 ms 408 KB Correct.
6 Correct 504 ms 1052 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 988 KB Correct.
2 Correct 86 ms 1364 KB Correct.
3 Correct 2324 ms 52140 KB Correct.
4 Correct 1306 ms 13392 KB Correct.
5 Correct 2420 ms 35088 KB Correct.
6 Correct 1638 ms 19272 KB Correct.
7 Correct 1290 ms 13660 KB Correct.
8 Correct 907 ms 2588 KB Correct.
9 Correct 458 ms 1148 KB Correct.
10 Correct 460 ms 996 KB Correct.
11 Correct 789 ms 1068 KB Correct.
12 Correct 486 ms 972 KB Correct.
13 Correct 536 ms 1276 KB Correct.
14 Correct 1125 ms 18104 KB Correct.
15 Correct 1018 ms 4824 KB Correct.
16 Correct 499 ms 1192 KB Correct.
17 Correct 584 ms 1052 KB Correct.
18 Correct 548 ms 960 KB Correct.
19 Correct 1283 ms 1048 KB Correct.
20 Correct 28 ms 392 KB Correct.
21 Correct 34 ms 824 KB Correct.
22 Correct 121 ms 2244 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1667 ms 2100 KB Correct.
2 Correct 248 ms 2900 KB Correct.
3 Execution timed out 3095 ms 175216 KB Time limit exceeded
4 Halted 0 ms 0 KB -