oj.uz

Submission #749251

# Submission time Handle Problem Language Result Execution time Memory
749251 2023-05-27T15:14:04 Z dxz05 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 29116 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]) {
                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 49 ms 412 KB Correct.
2 Correct 48 ms 412 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 644 KB Correct.
2 Correct 475 ms 468 KB Correct.
3 Correct 515 ms 512 KB Correct.
4 Correct 509 ms 504 KB Correct.
5 Correct 520 ms 524 KB Correct.
6 Correct 627 ms 2572 KB Correct.
7 Correct 832 ms 2492 KB Correct.
8 Correct 363 ms 4592 KB Correct.
9 Correct 234 ms 376 KB Correct.
10 Correct 214 ms 368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 532 KB Correct.
2 Correct 514 ms 536 KB Correct.
3 Correct 470 ms 588 KB Correct.
4 Correct 265 ms 376 KB Correct.
5 Correct 258 ms 500 KB Correct.
6 Correct 128 ms 1940 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 12088 KB Correct.
2 Correct 301 ms 560 KB Correct.
3 Correct 273 ms 616 KB Correct.
4 Correct 302 ms 592 KB Correct.
5 Correct 157 ms 356 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 600 KB Correct.
2 Correct 309 ms 616 KB Correct.
3 Correct 340 ms 512 KB Correct.
4 Correct 463 ms 2252 KB Correct.
5 Correct 136 ms 368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 624 KB Correct.
2 Correct 280 ms 540 KB Correct.
3 Correct 60 ms 13904 KB Correct.
4 Correct 272 ms 2068 KB Correct.
5 Correct 166 ms 356 KB Correct.
6 Correct 323 ms 440 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 556 KB Correct.
2 Correct 60 ms 596 KB Correct.
3 Correct 1562 ms 21588 KB Correct.
4 Correct 812 ms 5240 KB Correct.
5 Correct 1347 ms 13396 KB Correct.
6 Correct 925 ms 8988 KB Correct.
7 Correct 796 ms 5500 KB Correct.
8 Correct 601 ms 1112 KB Correct.
9 Correct 312 ms 588 KB Correct.
10 Correct 307 ms 588 KB Correct.
11 Correct 539 ms 776 KB Correct.
12 Correct 329 ms 624 KB Correct.
13 Correct 339 ms 608 KB Correct.
14 Correct 766 ms 11108 KB Correct.
15 Correct 668 ms 3028 KB Correct.
16 Correct 327 ms 644 KB Correct.
17 Correct 388 ms 488 KB Correct.
18 Correct 363 ms 552 KB Correct.
19 Correct 842 ms 468 KB Correct.
20 Correct 16 ms 356 KB Correct.
21 Correct 23 ms 456 KB Correct.
22 Correct 80 ms 1284 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 660 KB Correct.
2 Correct 129 ms 596 KB Correct.
3 Correct 2611 ms 29116 KB Correct.
4 Correct 889 ms 1832 KB Correct.
5 Execution timed out 3018 ms 13448 KB Time limit exceeded
6 Halted 0 ms 0 KB -