oj.uz

Submission #964399

# Submission time Handle Problem Language Result Execution time Memory
964399 2024-04-16T18:44:00 Z emad234 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 95240 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>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]) 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;
                if(x.F != H) q.push({x.F, u.k, (double)0});
                continue;
            }
            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;
                if (x.F != H)
                    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;
                if (x.F != H)
                    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 600 KB Correct.
2 Correct 17 ms 576 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 884 KB Correct.
2 Correct 25 ms 808 KB Correct.
3 Correct 23 ms 856 KB Correct.
4 Correct 25 ms 856 KB Correct.
5 Correct 31 ms 856 KB Correct.
6 Correct 27 ms 4176 KB Correct.
7 Correct 31 ms 4240 KB Correct.
8 Correct 13 ms 8284 KB Correct.
9 Correct 24 ms 560 KB Correct.
10 Correct 26 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 25 ms 760 KB Correct.
3 Correct 29 ms 880 KB Correct.
4 Correct 30 ms 348 KB Correct.
5 Correct 26 ms 348 KB Correct.
6 Correct 6 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 23476 KB Correct.
2 Correct 408 ms 984 KB Correct.
3 Correct 335 ms 860 KB Correct.
4 Correct 367 ms 860 KB Correct.
5 Correct 269 ms 568 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 836 KB Correct.
2 Correct 29 ms 856 KB Correct.
3 Correct 24 ms 832 KB Correct.
4 Correct 22 ms 3952 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 856 KB Correct.
2 Correct 21 ms 788 KB Correct.
3 Correct 48 ms 30732 KB Correct.
4 Correct 17 ms 2952 KB Correct.
5 Correct 24 ms 556 KB Correct.
6 Correct 35 ms 900 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 1280 KB Correct.
2 Correct 40 ms 1520 KB Correct.
3 Correct 1471 ms 30544 KB Correct.
4 Correct 1108 ms 7728 KB Correct.
5 Correct 954 ms 52656 KB Correct.
6 Correct 419 ms 27296 KB Correct.
7 Correct 1065 ms 8104 KB Correct.
8 Correct 919 ms 1628 KB Correct.
9 Correct 237 ms 1388 KB Correct.
10 Correct 260 ms 1188 KB Correct.
11 Correct 834 ms 1012 KB Correct.
12 Correct 253 ms 1392 KB Correct.
13 Correct 269 ms 1612 KB Correct.
14 Correct 838 ms 10844 KB Correct.
15 Correct 1116 ms 3120 KB Correct.
16 Correct 237 ms 1480 KB Correct.
17 Correct 309 ms 1556 KB Correct.
18 Correct 294 ms 1360 KB Correct.
19 Correct 873 ms 1888 KB Correct.
20 Correct 17 ms 604 KB Correct.
21 Correct 22 ms 1108 KB Correct.
22 Correct 28 ms 2268 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 2704 KB Correct.
2 Correct 92 ms 2868 KB Correct.
3 Correct 454 ms 71324 KB Correct.
4 Correct 2565 ms 4508 KB Correct.
5 Execution timed out 3049 ms 95240 KB Time limit exceeded
6 Halted 0 ms 0 KB -