oj.uz

Submission #964389

# Submission time Handle Problem Language Result Execution time Memory
964389 2024-04-16T18:29:58 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 97216 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,100);
    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 856 KB Correct.
2 Correct 19 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1624 KB Correct.
2 Correct 28 ms 1564 KB Correct.
3 Correct 25 ms 1624 KB Correct.
4 Correct 28 ms 1756 KB Correct.
5 Correct 31 ms 1728 KB Correct.
6 Correct 24 ms 5084 KB Correct.
7 Correct 31 ms 4900 KB Correct.
8 Correct 14 ms 8796 KB Correct.
9 Correct 31 ms 1112 KB Correct.
10 Correct 25 ms 1092 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1580 KB Correct.
2 Correct 30 ms 1604 KB Correct.
3 Correct 29 ms 1604 KB Correct.
4 Correct 27 ms 1120 KB Correct.
5 Correct 27 ms 1116 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 24508 KB Correct.
2 Correct 455 ms 1652 KB Correct.
3 Correct 386 ms 1864 KB Correct.
4 Correct 422 ms 1572 KB Correct.
5 Correct 305 ms 1372 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1604 KB Correct.
2 Correct 27 ms 1604 KB Correct.
3 Correct 25 ms 1604 KB Correct.
4 Correct 28 ms 4536 KB Correct.
5 Correct 22 ms 1144 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1636 KB Correct.
2 Correct 25 ms 1620 KB Correct.
3 Correct 49 ms 31980 KB Correct.
4 Correct 18 ms 3420 KB Correct.
5 Correct 26 ms 1112 KB Correct.
6 Correct 27 ms 1540 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 2216 KB Correct.
2 Correct 37 ms 2008 KB Correct.
3 Correct 1583 ms 32524 KB Correct.
4 Correct 1206 ms 9016 KB Correct.
5 Correct 1086 ms 68232 KB Correct.
6 Correct 413 ms 35840 KB Correct.
7 Correct 1146 ms 8692 KB Correct.
8 Correct 994 ms 2696 KB Correct.
9 Correct 270 ms 2336 KB Correct.
10 Correct 277 ms 2524 KB Correct.
11 Correct 922 ms 2164 KB Correct.
12 Correct 292 ms 2344 KB Correct.
13 Correct 285 ms 2368 KB Correct.
14 Correct 887 ms 12444 KB Correct.
15 Correct 1222 ms 4388 KB Correct.
16 Correct 278 ms 2624 KB Correct.
17 Correct 341 ms 2228 KB Correct.
18 Correct 327 ms 2312 KB Correct.
19 Correct 982 ms 3340 KB Correct.
20 Correct 20 ms 704 KB Correct.
21 Correct 24 ms 1360 KB Correct.
22 Correct 30 ms 3028 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1418 ms 7880 KB Correct.
2 Correct 154 ms 6412 KB Correct.
3 Correct 786 ms 97216 KB Correct.
4 Execution timed out 3019 ms 9692 KB Time limit exceeded
5 Halted 0 ms 0 KB -