oj.uz

Submission #964392

# Submission time Handle Problem Language Result Execution time Memory
964392 2024-04-16T18:34:04 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 71328 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<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 20 ms 604 KB Correct.
2 Correct 20 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Correct.
2 Correct 35 ms 916 KB Correct.
3 Correct 26 ms 856 KB Correct.
4 Correct 33 ms 864 KB Correct.
5 Correct 30 ms 1092 KB Correct.
6 Correct 25 ms 4432 KB Correct.
7 Correct 31 ms 4112 KB Correct.
8 Correct 15 ms 8284 KB Correct.
9 Correct 25 ms 348 KB Correct.
10 Correct 26 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 816 KB Correct.
2 Correct 30 ms 848 KB Correct.
3 Correct 26 ms 888 KB Correct.
4 Correct 38 ms 348 KB Correct.
5 Correct 27 ms 528 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 23380 KB Correct.
2 Correct 586 ms 836 KB Correct.
3 Correct 507 ms 1004 KB Correct.
4 Correct 509 ms 924 KB Correct.
5 Correct 430 ms 540 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 852 KB Correct.
2 Correct 26 ms 840 KB Correct.
3 Correct 30 ms 1000 KB Correct.
4 Correct 31 ms 3920 KB Correct.
5 Correct 23 ms 552 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 844 KB Correct.
2 Correct 28 ms 840 KB Correct.
3 Correct 49 ms 30848 KB Correct.
4 Correct 19 ms 2904 KB Correct.
5 Correct 26 ms 344 KB Correct.
6 Correct 26 ms 832 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 1624 KB Correct.
2 Correct 44 ms 1968 KB Correct.
3 Correct 1804 ms 31032 KB Correct.
4 Correct 1401 ms 7824 KB Correct.
5 Correct 1025 ms 69216 KB Correct.
6 Correct 467 ms 34228 KB Correct.
7 Correct 1349 ms 8216 KB Correct.
8 Correct 1254 ms 1816 KB Correct.
9 Correct 334 ms 1872 KB Correct.
10 Correct 359 ms 1944 KB Correct.
11 Correct 1195 ms 1284 KB Correct.
12 Correct 361 ms 1704 KB Correct.
13 Correct 350 ms 1844 KB Correct.
14 Correct 1073 ms 10940 KB Correct.
15 Correct 1474 ms 3124 KB Correct.
16 Correct 332 ms 1884 KB Correct.
17 Correct 427 ms 1472 KB Correct.
18 Correct 405 ms 1596 KB Correct.
19 Correct 1213 ms 2100 KB Correct.
20 Correct 28 ms 604 KB Correct.
21 Correct 31 ms 1264 KB Correct.
22 Correct 36 ms 2776 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 3848 KB Correct.
2 Correct 129 ms 3776 KB Correct.
3 Correct 722 ms 71328 KB Correct.
4 Execution timed out 3054 ms 5428 KB Time limit exceeded
5 Halted 0 ms 0 KB -