oj.uz

Submission #794114

# Submission time Handle Problem Language Result Execution time Memory
794114 2023-07-26T09:29:06 Z 12345678 Cyberland (APIO23_cyberland) C++17
97 / 100
 1688 ms 66840 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=31;

priority_queue<pair<double, pair<int, double>>, vector<pair<double, pair<int, double>>>, greater<pair<double, pair<int, double>>>> pq;
double dp[nx][kx], ans=DBL_MAX;

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) {
    vector<vector<pair<int, int>>> d(nx);
    for (int i=0; i<M; i++) d[x[i]].push_back({y[i], c[i]}), d[y[i]].push_back({x[i], c[i]});
    for (int i=0; i<N; i++) for (int j=0; j<kx; j++) dp[i][j]=DBL_MAX;
    dp[0][0]=0;
    pq.push({0, {0, 0}});
    while (!pq.empty())
    {
        auto cw=pq.top().first, cl=pq.top().second.second;
        auto ck=pq.top().second.first;
        pq.pop();
        //cout<<cw<<' '<<ck<<' '<<cl<<'\n';
        if (cl==H) continue;
        for (auto [v, w]:d[cl])
        {
            if (arr[v]==0&&dp[v][0]==DBL_MAX) pq.push({0, {0, v}}), dp[v][0]=0;
            if (dp[v][ck]>cw+w) pq.push({cw+w, {ck, v}}), dp[v][ck]=cw+w;
            if (arr[v]==2&&ck!=K) if (dp[v][ck+1]>(cw+w)/2) pq.push({(cw+w)/2, {ck+1, v}}), dp[v][ck+1]=(cw+w)/2; 
        }
    }
    ans=DBL_MAX;
    for (int i=0; i<=K; i++) ans=min(ans, dp[H][i]);
    if (ans==DBL_MAX) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 2836 KB Correct.
2 Correct 1598 ms 3168 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5312 KB Correct.
2 Correct 48 ms 5300 KB Correct.
3 Correct 46 ms 5300 KB Correct.
4 Correct 47 ms 5324 KB Correct.
5 Correct 48 ms 5292 KB Correct.
6 Correct 24 ms 5676 KB Correct.
7 Correct 32 ms 7776 KB Correct.
8 Correct 14 ms 8812 KB Correct.
9 Correct 194 ms 5080 KB Correct.
10 Correct 182 ms 5036 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5292 KB Correct.
2 Correct 46 ms 6068 KB Correct.
3 Correct 45 ms 6112 KB Correct.
4 Correct 185 ms 5296 KB Correct.
5 Correct 207 ms 5852 KB Correct.
6 Correct 7 ms 5332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 20560 KB Correct.
2 Correct 307 ms 3884 KB Correct.
3 Correct 272 ms 3944 KB Correct.
4 Correct 284 ms 4004 KB Correct.
5 Correct 400 ms 3496 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5244 KB Correct.
2 Correct 44 ms 5332 KB Correct.
3 Correct 47 ms 5328 KB Correct.
4 Correct 26 ms 5676 KB Correct.
5 Correct 179 ms 5036 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5292 KB Correct.
2 Correct 40 ms 6052 KB Correct.
3 Correct 53 ms 27612 KB Correct.
4 Correct 21 ms 7312 KB Correct.
5 Correct 184 ms 5876 KB Correct.
6 Correct 43 ms 5880 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 4268 KB Correct.
2 Correct 47 ms 5864 KB Correct.
3 Correct 587 ms 38320 KB Correct.
4 Correct 526 ms 11936 KB Correct.
5 Correct 1330 ms 66840 KB Correct.
6 Correct 626 ms 59800 KB Correct.
7 Correct 541 ms 13608 KB Correct.
8 Correct 565 ms 7776 KB Correct.
9 Correct 308 ms 6140 KB Correct.
10 Correct 294 ms 6300 KB Correct.
11 Correct 624 ms 7156 KB Correct.
12 Correct 319 ms 5136 KB Correct.
13 Correct 338 ms 6436 KB Correct.
14 Correct 423 ms 20724 KB Correct.
15 Correct 557 ms 10452 KB Correct.
16 Correct 303 ms 6748 KB Correct.
17 Correct 359 ms 6264 KB Correct.
18 Correct 364 ms 5208 KB Correct.
19 Correct 799 ms 5340 KB Correct.
20 Correct 43 ms 3316 KB Correct.
21 Correct 32 ms 5488 KB Correct.
22 Correct 47 ms 6556 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 802 ms 8200 KB Wrong Answer.
2 Halted 0 ms 0 KB -