oj.uz

Submission #964394

# Submission time Handle Problem Language Result Execution time Memory
964394 2024-04-16T18:36:49 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 96388 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
#define all(v) ((v).begin(), (v).end())
#define F first
#define S second
typedef long long ll;
#define pii pair<int, double>
using namespace std;
const int mod = 1e9 + 7;
const int mxN = 4e6 + 5;
struct path
{
    int 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 18 ms 604 KB Correct.
2 Correct 18 ms 496 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 860 KB Correct.
2 Correct 27 ms 808 KB Correct.
3 Correct 28 ms 860 KB Correct.
4 Correct 26 ms 812 KB Correct.
5 Correct 24 ms 908 KB Correct.
6 Correct 21 ms 4168 KB Correct.
7 Correct 27 ms 4336 KB Correct.
8 Correct 13 ms 8284 KB Correct.
9 Correct 25 ms 356 KB Correct.
10 Correct 30 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 800 KB Correct.
2 Correct 26 ms 760 KB Correct.
3 Correct 23 ms 860 KB Correct.
4 Correct 33 ms 348 KB Correct.
5 Correct 32 ms 552 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 23468 KB Correct.
2 Correct 392 ms 832 KB Correct.
3 Correct 343 ms 900 KB Correct.
4 Correct 360 ms 856 KB Correct.
5 Correct 264 ms 592 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 836 KB Correct.
2 Correct 24 ms 856 KB Correct.
3 Correct 23 ms 832 KB Correct.
4 Correct 23 ms 3948 KB Correct.
5 Correct 22 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 876 KB Correct.
2 Correct 22 ms 788 KB Correct.
3 Correct 48 ms 30804 KB Correct.
4 Correct 17 ms 2880 KB Correct.
5 Correct 24 ms 344 KB Correct.
6 Correct 24 ms 852 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 1492 KB Correct.
2 Correct 32 ms 1564 KB Correct.
3 Correct 1394 ms 30648 KB Correct.
4 Correct 1078 ms 7628 KB Correct.
5 Correct 948 ms 51776 KB Correct.
6 Correct 362 ms 26812 KB Correct.
7 Correct 1066 ms 8076 KB Correct.
8 Correct 905 ms 1832 KB Correct.
9 Correct 250 ms 1416 KB Correct.
10 Correct 253 ms 1416 KB Correct.
11 Correct 819 ms 1068 KB Correct.
12 Correct 261 ms 1420 KB Correct.
13 Correct 251 ms 1492 KB Correct.
14 Correct 848 ms 10816 KB Correct.
15 Correct 1123 ms 3096 KB Correct.
16 Correct 260 ms 1660 KB Correct.
17 Correct 303 ms 1348 KB Correct.
18 Correct 289 ms 1332 KB Correct.
19 Correct 860 ms 1640 KB Correct.
20 Correct 18 ms 600 KB Correct.
21 Correct 22 ms 1068 KB Correct.
22 Correct 27 ms 2268 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 2772 KB Correct.
2 Correct 94 ms 2864 KB Correct.
3 Correct 488 ms 71316 KB Correct.
4 Correct 2562 ms 4504 KB Correct.
5 Execution timed out 3050 ms 96388 KB Time limit exceeded
6 Halted 0 ms 0 KB -