oj.uz

Submission #749248

# Submission time Handle Problem Language Result Execution time Memory
749248 2023-05-27T15:12:32 Z dxz05 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 27420 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;

    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]) {
                dp[u][k % T] = min(dp[u][k % T], dp[v][k % T] + w);
                if (arr[u] == 0) {
                    dp[u][k % T] = 0;
                }

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

                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 58 ms 340 KB Correct.
2 Correct 51 ms 472 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 532 KB Correct.
2 Correct 497 ms 536 KB Correct.
3 Correct 488 ms 656 KB Correct.
4 Correct 493 ms 492 KB Correct.
5 Correct 474 ms 468 KB Correct.
6 Correct 558 ms 2452 KB Correct.
7 Correct 753 ms 2544 KB Correct.
8 Correct 378 ms 4688 KB Correct.
9 Correct 242 ms 352 KB Correct.
10 Correct 244 ms 364 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 524 KB Correct.
2 Correct 534 ms 516 KB Correct.
3 Correct 511 ms 544 KB Correct.
4 Correct 284 ms 480 KB Correct.
5 Correct 265 ms 356 KB Correct.
6 Correct 120 ms 1940 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 11748 KB Correct.
2 Correct 299 ms 716 KB Correct.
3 Correct 253 ms 564 KB Correct.
4 Correct 273 ms 532 KB Correct.
5 Correct 155 ms 360 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 496 KB Correct.
2 Correct 324 ms 500 KB Correct.
3 Correct 363 ms 532 KB Correct.
4 Correct 456 ms 2216 KB Correct.
5 Correct 151 ms 376 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 536 KB Correct.
2 Correct 316 ms 664 KB Correct.
3 Correct 68 ms 13800 KB Correct.
4 Correct 260 ms 1928 KB Correct.
5 Correct 184 ms 360 KB Correct.
6 Correct 338 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 656 KB Correct.
2 Correct 60 ms 536 KB Correct.
3 Correct 1560 ms 21400 KB Correct.
4 Correct 841 ms 4980 KB Correct.
5 Correct 1393 ms 12988 KB Correct.
6 Correct 1085 ms 9056 KB Correct.
7 Correct 915 ms 5476 KB Correct.
8 Correct 639 ms 1008 KB Correct.
9 Correct 335 ms 568 KB Correct.
10 Correct 347 ms 524 KB Correct.
11 Correct 606 ms 720 KB Correct.
12 Correct 369 ms 464 KB Correct.
13 Correct 371 ms 580 KB Correct.
14 Correct 822 ms 10828 KB Correct.
15 Correct 751 ms 3044 KB Correct.
16 Correct 387 ms 580 KB Correct.
17 Correct 421 ms 540 KB Correct.
18 Correct 415 ms 632 KB Correct.
19 Correct 990 ms 468 KB Correct.
20 Correct 21 ms 364 KB Correct.
21 Correct 26 ms 452 KB Correct.
22 Correct 92 ms 1352 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 484 KB Correct.
2 Correct 152 ms 596 KB Correct.
3 Execution timed out 3035 ms 27420 KB Time limit exceeded
4 Halted 0 ms 0 KB -