oj.uz

Submission #964390

# Submission time Handle Problem Language Result Execution time Memory
964390 2024-04-16T18:31:50 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 1549 ms 68980 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,64);
    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 19 ms 524 KB Correct.
2 Correct 19 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Correct.
2 Correct 27 ms 916 KB Correct.
3 Correct 25 ms 860 KB Correct.
4 Correct 26 ms 904 KB Correct.
5 Correct 33 ms 840 KB Correct.
6 Correct 29 ms 4436 KB Correct.
7 Correct 30 ms 4112 KB Correct.
8 Correct 14 ms 8284 KB Correct.
9 Correct 26 ms 504 KB Correct.
10 Correct 25 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 816 KB Correct.
2 Correct 33 ms 828 KB Correct.
3 Correct 25 ms 860 KB Correct.
4 Correct 28 ms 552 KB Correct.
5 Correct 30 ms 344 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 23480 KB Correct.
2 Correct 464 ms 864 KB Correct.
3 Correct 399 ms 884 KB Correct.
4 Correct 411 ms 872 KB Correct.
5 Correct 300 ms 532 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 848 KB Correct.
2 Correct 25 ms 836 KB Correct.
3 Correct 31 ms 840 KB Correct.
4 Correct 24 ms 3916 KB Correct.
5 Correct 22 ms 564 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 876 KB Correct.
2 Correct 23 ms 840 KB Correct.
3 Correct 55 ms 30844 KB Correct.
4 Correct 18 ms 2904 KB Correct.
5 Correct 31 ms 540 KB Correct.
6 Correct 35 ms 804 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 1484 KB Correct.
2 Correct 36 ms 2060 KB Correct.
3 Correct 1549 ms 31092 KB Correct.
4 Correct 1174 ms 8052 KB Correct.
5 Correct 1108 ms 68980 KB Correct.
6 Correct 477 ms 34240 KB Correct.
7 Correct 1147 ms 8480 KB Correct.
8 Correct 979 ms 1708 KB Correct.
9 Correct 277 ms 1832 KB Correct.
10 Correct 291 ms 1864 KB Correct.
11 Correct 911 ms 1072 KB Correct.
12 Correct 285 ms 1708 KB Correct.
13 Correct 287 ms 1928 KB Correct.
14 Correct 885 ms 10940 KB Correct.
15 Correct 1207 ms 3276 KB Correct.
16 Correct 284 ms 1892 KB Correct.
17 Correct 341 ms 1588 KB Correct.
18 Correct 319 ms 1576 KB Correct.
19 Correct 968 ms 2232 KB Correct.
20 Correct 20 ms 604 KB Correct.
21 Correct 24 ms 1260 KB Correct.
22 Correct 30 ms 2776 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 3580 KB Correct.
2 Correct 97 ms 3648 KB Correct.
3 Incorrect 572 ms 66624 KB Wrong Answer.
4 Halted 0 ms 0 KB -