oj.uz

Submission #964391

# Submission time Handle Problem Language Result Execution time Memory
964391 2024-04-16T18:32:37 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 130692 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(), (v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<ll, double>
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 4e6 + 5;
struct path
{
    ll i, k;
    double val;
};
bool operator<(path a, path b)
{
    return a.val < b.val;
}
bool operator>(path a, path b)
{
    return a.val > b.val;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
    vector<vector<double>>dp;  
    vector<int>vis;
    vector<vector<pii>> v;
    dp.resize(N + 3);
    vis.resize(N + 3);
    v.resize(N + 3);
    K = min(K,70);
    for (int i = 0; i < M; i++)
    {
        v[x[i]].push_back({y[i], (double)c[i]});
        v[y[i]].push_back({x[i], (double)c[i]});
    }
    for(int i = 0;i < N;i++){
        dp[i].resize(K + 3);
        for(int j = 0;j <= K;j++){
            dp[i][j] = 1e18;
        }
    }
    priority_queue<path,vector<path>,greater<path>>q;
    q.push({0,0,0});
    dp[0][0] = 0;
    while(q.size()){
        auto u = q.top();
        q.pop();
        if(u.val < dp[u.i][u.k] || u.i == H) continue;
        for(auto x : v[u.i]){
            if (arr[x.F] == 0 && dp[x.F][u.k] != (double)0)
            {
                dp[x.F][u.k] = (double)0;
                q.push({x.F, u.k, (double)0});
            }
            if(dp[x.F][u.k] > dp[u.i][u.k] + x.S){
                dp[x.F][u.k] = dp[u.i][u.k] + x.S;
                q.push({x.F,u.k,dp[x.F][u.k]});
            }
            if(u.k != K && arr[u.i] == 2 && dp[x.F][u.k + 1] > dp[u.i][u.k] / 2 + x.S){
                dp[x.F][u.k + 1] = dp[u.i][u.k] / 2 + x.S;
                q.push({x.F,u.k + 1,dp[x.F][u.k + 1]});
            }
        }
    }
    double ans = 1e18;
    for(int i = 0;i <= K;i++){
        ans = min(ans,dp[H][i]);
    }
    return ans == 1e18 ? -1 : ans;
}

// int main()
// {
//     int T;
//     assert(1 == scanf("%d", &T));
//     while (T--)
//     {
//         int N, M, K, H;
//         assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
//         vector<int> x(M);
//         vector<int> y(M);
//         vector<int> c(M);
//         vector<int> arr(N);
//         for (int i = 0; i < N; i++)
//             assert(1 == scanf("%d", &arr[i]));
//         for (int i = 0; i < M; i++)
//             assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
//         printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
//     }
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 480 KB Correct.
2 Correct 19 ms 556 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 860 KB Correct.
2 Correct 28 ms 892 KB Correct.
3 Correct 25 ms 856 KB Correct.
4 Correct 27 ms 824 KB Correct.
5 Correct 27 ms 840 KB Correct.
6 Correct 23 ms 4436 KB Correct.
7 Correct 30 ms 4108 KB Correct.
8 Correct 17 ms 8436 KB Correct.
9 Correct 25 ms 504 KB Correct.
10 Correct 30 ms 524 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 840 KB Correct.
2 Correct 32 ms 856 KB Correct.
3 Correct 25 ms 856 KB Correct.
4 Correct 31 ms 344 KB Correct.
5 Correct 34 ms 604 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 23480 KB Correct.
2 Correct 473 ms 940 KB Correct.
3 Correct 387 ms 1056 KB Correct.
4 Correct 413 ms 928 KB Correct.
5 Correct 301 ms 592 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 856 KB Correct.
2 Correct 25 ms 856 KB Correct.
3 Correct 30 ms 816 KB Correct.
4 Correct 24 ms 4148 KB Correct.
5 Correct 23 ms 568 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 852 KB Correct.
2 Correct 23 ms 848 KB Correct.
3 Correct 53 ms 30800 KB Correct.
4 Correct 18 ms 2956 KB Correct.
5 Correct 27 ms 348 KB Correct.
6 Correct 25 ms 804 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 1488 KB Correct.
2 Correct 36 ms 2028 KB Correct.
3 Correct 1527 ms 31032 KB Correct.
4 Correct 1138 ms 7760 KB Correct.
5 Correct 1126 ms 68076 KB Correct.
6 Correct 465 ms 35092 KB Correct.
7 Correct 1143 ms 8240 KB Correct.
8 Correct 1014 ms 1772 KB Correct.
9 Correct 263 ms 1764 KB Correct.
10 Correct 287 ms 1812 KB Correct.
11 Correct 898 ms 1028 KB Correct.
12 Correct 287 ms 1716 KB Correct.
13 Correct 279 ms 1844 KB Correct.
14 Correct 904 ms 10896 KB Correct.
15 Correct 1216 ms 3156 KB Correct.
16 Correct 267 ms 2188 KB Correct.
17 Correct 355 ms 1620 KB Correct.
18 Correct 322 ms 1596 KB Correct.
19 Correct 1006 ms 2036 KB Correct.
20 Correct 20 ms 624 KB Correct.
21 Correct 24 ms 1276 KB Correct.
22 Correct 30 ms 2872 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 3796 KB Correct.
2 Correct 117 ms 3672 KB Correct.
3 Correct 578 ms 71332 KB Correct.
4 Correct 2779 ms 5364 KB Correct.
5 Execution timed out 3037 ms 130692 KB Time limit exceeded
6 Halted 0 ms 0 KB -