oj.uz

Submission #964388

# Submission time Handle Problem Language Result Execution time Memory
964388 2024-04-16T18:29:14 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 1557 ms 2097152 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);
    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 25 ms 848 KB Correct.
2 Correct 19 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1624 KB Correct.
2 Correct 27 ms 1936 KB Correct.
3 Correct 36 ms 1876 KB Correct.
4 Correct 28 ms 1880 KB Correct.
5 Correct 27 ms 1860 KB Correct.
6 Correct 23 ms 5204 KB Correct.
7 Correct 30 ms 4880 KB Correct.
8 Correct 14 ms 8796 KB Correct.
9 Correct 25 ms 1316 KB Correct.
10 Correct 27 ms 1376 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1796 KB Correct.
2 Correct 28 ms 1780 KB Correct.
3 Correct 26 ms 1624 KB Correct.
4 Correct 27 ms 1384 KB Correct.
5 Correct 28 ms 1420 KB Correct.
6 Correct 6 ms 3672 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 24876 KB Correct.
2 Correct 475 ms 2028 KB Correct.
3 Correct 398 ms 1896 KB Correct.
4 Correct 412 ms 1776 KB Correct.
5 Correct 307 ms 1364 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1752 KB Correct.
2 Correct 25 ms 1880 KB Correct.
3 Correct 27 ms 1840 KB Correct.
4 Correct 24 ms 4688 KB Correct.
5 Correct 22 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1752 KB Correct.
2 Correct 28 ms 1724 KB Correct.
3 Correct 49 ms 32760 KB Correct.
4 Correct 21 ms 3596 KB Correct.
5 Correct 31 ms 1308 KB Correct.
6 Correct 25 ms 1764 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 2380 KB Correct.
2 Correct 37 ms 2220 KB Correct.
3 Correct 1557 ms 33464 KB Correct.
4 Correct 1150 ms 10312 KB Correct.
5 Correct 1113 ms 69196 KB Correct.
6 Correct 467 ms 36272 KB Correct.
7 Correct 1158 ms 9180 KB Correct.
8 Correct 971 ms 3356 KB Correct.
9 Correct 274 ms 2596 KB Correct.
10 Correct 278 ms 2620 KB Correct.
11 Correct 905 ms 2768 KB Correct.
12 Correct 301 ms 2488 KB Correct.
13 Correct 281 ms 2816 KB Correct.
14 Correct 917 ms 12580 KB Correct.
15 Correct 1223 ms 5132 KB Correct.
16 Correct 277 ms 2876 KB Correct.
17 Correct 339 ms 2680 KB Correct.
18 Correct 323 ms 2752 KB Correct.
19 Correct 992 ms 4132 KB Correct.
20 Correct 20 ms 604 KB Correct.
21 Correct 24 ms 1228 KB Correct.
22 Correct 30 ms 3032 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1249 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -