oj.uz

Submission #749257

# Submission time Handle Problem Language Result Execution time Memory
749257 2023-05-27T15:16:21 Z dxz05 Cyberland (APIO23_cyberland) C++17
100 / 100
 2111 ms 29248 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;

    const int T = 5;

    vector<vector<double>> dp(N, vector<double>(T, INF));
    for (int v : zeros){
        dp[v].assign(T, 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 + T - 1) % T] == INF) continue;
                dp[i][k % T] = min(dp[i][k % T], dp[i][(k + T - 1) % T]);

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

        priority_queue<pair<double, int>> pq;
        for (int i = 0; i < N; i++) {
            if (dp[i][k % T] != INF) pq.emplace(-dp[i][k % T], 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 % T] + w;
                if (arr[u] == 0) new_val = 0;

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

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

        }

        for (int v = 0; v < N; v++){
            dp[v][(k + T - 2) % T] = INF;
        }
        for (int v : zeros) dp[v][(k + T - 2) % T] = 0;

        for (auto [v, w]: g[H]) {
            if (dp[v][k % T] == INF) continue;
            if (arr[H] == 0) return 0;

            ans = min(ans, dp[v][k % T] + w);
            if (k < K && arr[H] == 2) {
                ans = min(ans, (dp[v][k % T] + 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 340 KB Correct.
2 Correct 47 ms 472 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 504 KB Correct.
2 Correct 169 ms 636 KB Correct.
3 Correct 174 ms 500 KB Correct.
4 Correct 163 ms 508 KB Correct.
5 Correct 151 ms 460 KB Correct.
6 Correct 209 ms 2452 KB Correct.
7 Correct 291 ms 2428 KB Correct.
8 Correct 125 ms 4604 KB Correct.
9 Correct 98 ms 364 KB Correct.
10 Correct 101 ms 376 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 504 KB Correct.
2 Correct 183 ms 500 KB Correct.
3 Correct 163 ms 484 KB Correct.
4 Correct 112 ms 368 KB Correct.
5 Correct 112 ms 372 KB Correct.
6 Correct 50 ms 2004 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 11980 KB Correct.
2 Correct 126 ms 596 KB Correct.
3 Correct 107 ms 608 KB Correct.
4 Correct 126 ms 548 KB Correct.
5 Correct 79 ms 376 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 592 KB Correct.
2 Correct 90 ms 544 KB Correct.
3 Correct 92 ms 556 KB Correct.
4 Correct 119 ms 2260 KB Correct.
5 Correct 68 ms 372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 560 KB Correct.
2 Correct 84 ms 560 KB Correct.
3 Correct 72 ms 13804 KB Correct.
4 Correct 82 ms 1956 KB Correct.
5 Correct 76 ms 372 KB Correct.
6 Correct 102 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 560 KB Correct.
2 Correct 16 ms 596 KB Correct.
3 Correct 972 ms 21712 KB Correct.
4 Correct 449 ms 5032 KB Correct.
5 Correct 518 ms 13032 KB Correct.
6 Correct 163 ms 7976 KB Correct.
7 Correct 460 ms 5496 KB Correct.
8 Correct 326 ms 1040 KB Correct.
9 Correct 99 ms 588 KB Correct.
10 Correct 105 ms 544 KB Correct.
11 Correct 302 ms 688 KB Correct.
12 Correct 111 ms 468 KB Correct.
13 Correct 104 ms 516 KB Correct.
14 Correct 399 ms 11004 KB Correct.
15 Correct 357 ms 3180 KB Correct.
16 Correct 103 ms 520 KB Correct.
17 Correct 132 ms 468 KB Correct.
18 Correct 119 ms 548 KB Correct.
19 Correct 340 ms 540 KB Correct.
20 Correct 8 ms 348 KB Correct.
21 Correct 12 ms 468 KB Correct.
22 Correct 13 ms 1108 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 468 KB Correct.
2 Correct 29 ms 596 KB Correct.
3 Correct 1450 ms 29248 KB Correct.
4 Correct 488 ms 1720 KB Correct.
5 Correct 984 ms 13140 KB Correct.
6 Correct 347 ms 7672 KB Correct.
7 Correct 705 ms 9092 KB Correct.
8 Correct 426 ms 800 KB Correct.
9 Correct 191 ms 568 KB Correct.
10 Correct 199 ms 516 KB Correct.
11 Correct 238 ms 460 KB Correct.
12 Correct 221 ms 532 KB Correct.
13 Correct 211 ms 592 KB Correct.
14 Correct 1592 ms 12104 KB Correct.
15 Correct 2111 ms 10976 KB Correct.
16 Correct 725 ms 4476 KB Correct.
17 Correct 456 ms 1160 KB Correct.
18 Correct 198 ms 484 KB Correct.
19 Correct 241 ms 632 KB Correct.
20 Correct 227 ms 568 KB Correct.
21 Correct 725 ms 536 KB Correct.
22 Correct 13 ms 340 KB Correct.
23 Correct 16 ms 444 KB Correct.
24 Correct 23 ms 1108 KB Correct.