oj.uz

Submission #749238

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

using namespace std;

vector<vector<pair<int, double>>> 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, 70);

    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 double INF = 2e15;

    vector<vector<double>> dp(N, vector<double>(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<double, 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);
            }

        }

    }

    double 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 69 ms 440 KB Correct.
2 Correct 49 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 696 KB Correct.
2 Correct 481 ms 656 KB Correct.
3 Correct 460 ms 840 KB Correct.
4 Correct 492 ms 732 KB Correct.
5 Correct 485 ms 756 KB Correct.
6 Correct 571 ms 4436 KB Correct.
7 Correct 737 ms 4376 KB Correct.
8 Correct 352 ms 8556 KB Correct.
9 Correct 287 ms 392 KB Correct.
10 Correct 233 ms 460 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 716 KB Correct.
2 Correct 489 ms 680 KB Correct.
3 Correct 443 ms 728 KB Correct.
4 Correct 268 ms 392 KB Correct.
5 Correct 254 ms 384 KB Correct.
6 Correct 118 ms 3704 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 23608 KB Correct.
2 Correct 274 ms 776 KB Correct.
3 Correct 245 ms 1024 KB Correct.
4 Correct 256 ms 720 KB Correct.
5 Correct 170 ms 516 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 752 KB Correct.
2 Correct 304 ms 668 KB Correct.
3 Correct 362 ms 728 KB Correct.
4 Correct 454 ms 4172 KB Correct.
5 Correct 154 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 716 KB Correct.
2 Correct 311 ms 716 KB Correct.
3 Correct 84 ms 29304 KB Correct.
4 Correct 284 ms 3064 KB Correct.
5 Correct 175 ms 468 KB Correct.
6 Correct 322 ms 768 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 732 KB Correct.
2 Correct 58 ms 852 KB Correct.
3 Correct 1589 ms 31924 KB Correct.
4 Correct 815 ms 8220 KB Correct.
5 Correct 1548 ms 20700 KB Correct.
6 Correct 913 ms 11220 KB Correct.
7 Correct 840 ms 8208 KB Correct.
8 Correct 630 ms 1664 KB Correct.
9 Correct 337 ms 760 KB Correct.
10 Correct 304 ms 728 KB Correct.
11 Correct 532 ms 824 KB Correct.
12 Correct 359 ms 776 KB Correct.
13 Correct 346 ms 716 KB Correct.
14 Correct 822 ms 11696 KB Correct.
15 Correct 668 ms 3288 KB Correct.
16 Correct 328 ms 840 KB Correct.
17 Correct 401 ms 776 KB Correct.
18 Correct 379 ms 724 KB Correct.
19 Correct 853 ms 844 KB Correct.
20 Correct 18 ms 340 KB Correct.
21 Correct 23 ms 608 KB Correct.
22 Correct 80 ms 1436 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 1036 KB Correct.
2 Correct 132 ms 1364 KB Correct.
3 Execution timed out 3070 ms 79312 KB Time limit exceeded
4 Halted 0 ms 0 KB -