oj.uz

Submission #749263

# Submission time Handle Problem Language Result Execution time Memory
749263 2023-05-27T15:27:52 Z dxz05 Cyberland (APIO23_cyberland) C++17
100 / 100
 2048 ms 80808 KB 
#pragma GCC optimize("Ofast,O1,O2,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#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);
    }

    double ans = INF;

    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]) {
                double new_val = dp[v][k] + w;
                if (arr[u] == 0) new_val = 0;

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

                if (dp[u][k] > new_val) {
                    dp[u][k] = new_val;
                    pq.emplace(-dp[u][k], u);
                }
            }

        }

        for (auto [v, w]: g[H]) {
            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 46 ms 420 KB Correct.
2 Correct 44 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 716 KB Correct.
2 Correct 156 ms 720 KB Correct.
3 Correct 156 ms 716 KB Correct.
4 Correct 156 ms 716 KB Correct.
5 Correct 155 ms 716 KB Correct.
6 Correct 209 ms 4420 KB Correct.
7 Correct 270 ms 4384 KB Correct.
8 Correct 153 ms 8544 KB Correct.
9 Correct 95 ms 396 KB Correct.
10 Correct 92 ms 396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 692 KB Correct.
2 Correct 169 ms 684 KB Correct.
3 Correct 156 ms 744 KB Correct.
4 Correct 106 ms 340 KB Correct.
5 Correct 111 ms 396 KB Correct.
6 Correct 49 ms 3576 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 23964 KB Correct.
2 Correct 115 ms 792 KB Correct.
3 Correct 99 ms 784 KB Correct.
4 Correct 106 ms 844 KB Correct.
5 Correct 74 ms 388 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 792 KB Correct.
2 Correct 79 ms 720 KB Correct.
3 Correct 86 ms 720 KB Correct.
4 Correct 115 ms 4208 KB Correct.
5 Correct 55 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 704 KB Correct.
2 Correct 76 ms 696 KB Correct.
3 Correct 88 ms 29304 KB Correct.
4 Correct 78 ms 3064 KB Correct.
5 Correct 67 ms 384 KB Correct.
6 Correct 90 ms 740 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 760 KB Correct.
2 Correct 16 ms 852 KB Correct.
3 Correct 989 ms 31884 KB Correct.
4 Correct 484 ms 8016 KB Correct.
5 Correct 537 ms 20528 KB Correct.
6 Correct 168 ms 9984 KB Correct.
7 Correct 446 ms 8060 KB Correct.
8 Correct 329 ms 1588 KB Correct.
9 Correct 92 ms 748 KB Correct.
10 Correct 95 ms 740 KB Correct.
11 Correct 276 ms 800 KB Correct.
12 Correct 108 ms 1008 KB Correct.
13 Correct 100 ms 796 KB Correct.
14 Correct 397 ms 11696 KB Correct.
15 Correct 354 ms 3244 KB Correct.
16 Correct 100 ms 772 KB Correct.
17 Correct 117 ms 756 KB Correct.
18 Correct 117 ms 784 KB Correct.
19 Correct 326 ms 724 KB Correct.
20 Correct 7 ms 340 KB Correct.
21 Correct 10 ms 604 KB Correct.
22 Correct 12 ms 1304 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 1008 KB Correct.
2 Correct 29 ms 1364 KB Correct.
3 Correct 1944 ms 80808 KB Correct.
4 Correct 457 ms 3116 KB Correct.
5 Correct 1163 ms 31740 KB Correct.
6 Correct 352 ms 13532 KB Correct.
7 Correct 674 ms 14508 KB Correct.
8 Correct 376 ms 1424 KB Correct.
9 Correct 173 ms 1208 KB Correct.
10 Correct 178 ms 1004 KB Correct.
11 Correct 219 ms 564 KB Correct.
12 Correct 202 ms 1156 KB Correct.
13 Correct 183 ms 1064 KB Correct.
14 Correct 1639 ms 32004 KB Correct.
15 Correct 2048 ms 36556 KB Correct.
16 Correct 753 ms 12952 KB Correct.
17 Correct 434 ms 3072 KB Correct.
18 Correct 181 ms 1208 KB Correct.
19 Correct 233 ms 1040 KB Correct.
20 Correct 217 ms 1016 KB Correct.
21 Correct 697 ms 1052 KB Correct.
22 Correct 11 ms 340 KB Correct.
23 Correct 15 ms 888 KB Correct.
24 Correct 23 ms 1492 KB Correct.