oj.uz

Submission #751000

# Submission time Handle Problem Language Result Execution time Memory
751000 2023-05-30T18:23:13 Z Hona_Nguyen Cyberland (APIO23_cyberland) C++17
97 / 100
 1613 ms 62880 KB 
#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;


double sub_2_5(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    struct ii{
        int id;
        double w;
    };
    struct cmp{
        bool operator () (ii A, ii B){
            return A.w > B.w;
        }
    };

    priority_queue<ii, vector<ii>, cmp> pq;

    vector<double> dp(N, (double)(1e15));
    vector<vector<pair<int,int>>> G(N);

    for(int i=0;i<M;i++){
        G[x[i]].push_back({y[i], c[i]});
        G[y[i]].push_back({x[i], c[i]});
    }

    dp[0] = 0;
    pq.push({0,dp[0]});

    while(pq.size()){
        ii u = pq.top();
        pq.pop();
        if(dp[u.id] < u.w) continue;
        for(pair<int,int> v: G[u.id]){
            if(dp[u.id] + v.second < dp[v.first]){
                dp[v.first] = dp[u.id] + v.second;
                pq.push({v.first, dp[v.first]});
            }
        }
    }
    if(dp[H] == (double)(1e15)) dp[H] = -1;
    return dp[H];
}

double sub_3_6(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    struct ii{
        int id;
        double w;
    };
    struct cmp{
        bool operator () (ii A, ii B){
            return A.w > B.w;
        }
    };

    priority_queue<ii, vector<ii>, cmp> pq;

    vector<double> dp(N, (double)(1e15));
    vector<vector<pair<int,int>>> G(N);

    for(int i=0;i<M;i++){
        G[x[i]].push_back({y[i], c[i]});
        G[y[i]].push_back({x[i], c[i]});
    }

    dp[0] = 0;
    pq.push({0,dp[0]});

    vector<bool> vis(N,false);
    queue<int> Q;
    Q.push(0);
    vis[0] = true;

    while(Q.size()){
        int u = Q.front();
        Q.pop();
        for(pair<int,int> v: G[u]){
            if(vis[v.first] == true || v.first == H) continue;
            vis[v.first] = true;
            Q.push(v.first);
        }
    }

    for(int i=1;i<N;i++){
        if(arr[i] == 0 && vis[i] == true){
            dp[i] = 0;
            pq.push({i,dp[i]});
        }
    }

    while(pq.size()){
        ii u = pq.top();
        pq.pop();
        if(dp[u.id] < u.w) continue;
        for(pair<int,int> v: G[u.id]){
            if(dp[u.id] + v.second < dp[v.first]){
                dp[v.first] = dp[u.id] + v.second;
                pq.push({v.first, dp[v.first]});
            }
        }
    }
    if(dp[H] == (double)(1e15)) dp[H] = -1;
    return dp[H];
}

double sub_1_4_7(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    struct ii{
        int id;
        int div2;
        double w;
    };
    struct cmp{
        bool operator () (ii A, ii B){
            return A.w > B.w;
        }
    };

    priority_queue<ii, vector<ii>, cmp> pq;

    vector<vector<double>> dp(N, vector<double> (K+2, (double)(1e15)));
    vector<vector<pair<int,int>>> G(N);

    for(int i=0;i<M;i++){
        G[x[i]].push_back({y[i], c[i]});
        G[y[i]].push_back({x[i], c[i]});
    }

    dp[0][0] = 0;
    pq.push({0,0,dp[0][0]});

    vector<bool> vis(N,false);
    queue<int> Q;
    Q.push(0);
    vis[0] = true;

    while(Q.size()){
        int u = Q.front();
        Q.pop();
        for(pair<int,int> v: G[u]){
            if(vis[v.first] == true || v.first == H) continue;
            vis[v.first] = true;
            Q.push(v.first);
        }
    }

    for(int i=1;i<N;i++){
        if(arr[i] == 0 && vis[i] == true){
            dp[i][0] = 0;
            pq.push({i,0,dp[i][0]});
        }
    }

    while(pq.size()){
        ii u = pq.top();
        pq.pop();
        if(dp[u.id][u.div2] < u.w) continue;
        if(u.id == H) continue;
        for(pair<int,int> v: G[u.id]){
            if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2]){
                dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
                pq.push({v.first, u.div2, dp[v.first][u.div2]});
            }
            double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
            if(u.div2 + 1 <= K && arr[v.first] == 2){
                if(tmp < dp[v.first][u.div2+1]){
                    dp[v.first][u.div2+1] = tmp;
                    pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
                }
            }
        }
    }

    double ans = (double)(1e15);
    for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
    if(ans == (double)(1e15)) ans = -1;
    return ans;
}

double sub_8(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    struct ii{
        int id;
        int div2;
        double w;
    };
    struct cmp{
        bool operator () (ii A, ii B){
            return A.w > B.w;
        }
    };

    priority_queue<ii, vector<ii>, cmp> pq;

    vector<vector<double>> dp(N, vector<double> (K+2, (double)(1e15)));
    vector<vector<pair<int,int>>> G(N);

    for(int i=0;i<M;i++){
        G[x[i]].push_back({y[i], c[i]});
        G[y[i]].push_back({x[i], c[i]});
    }

    dp[0][0] = 0;
    pq.push({0,0,dp[0][0]});

    vector<bool> vis(N,false);
    queue<int> Q;
    Q.push(0);
    vis[0] = true;

    while(Q.size()){
        int u = Q.front();
        Q.pop();
        for(pair<int,int> v: G[u]){
            if(vis[v.first] == true || v.first == H) continue;
            vis[v.first] = true;
            Q.push(v.first);
        }
    }

    for(int i=1;i<N;i++){
        if(arr[i] == 0 && vis[i] == true){
            dp[i][0] = 0;
            pq.push({i,0,dp[i][0]});
        }
    }

    while(pq.size()){
        ii u = pq.top();
        pq.pop();
        if(dp[u.id][u.div2] < u.w) continue;
        if(u.id == H) continue;
        for(pair<int,int> v: G[u.id]){
            if(dp[u.id][u.div2] + v.second < dp[v.first][u.div2]){
                dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
                pq.push({v.first, u.div2, dp[v.first][u.div2]});
            }
            double tmp = (dp[u.id][u.div2] + v.second) / 2.0;
            if(u.div2 + 1 <= K && arr[v.first] == 2){
                if(tmp < dp[v.first][u.div2+1]){
                    dp[v.first][u.div2+1] = tmp;
                    pq.push({v.first, u.div2+1, dp[v.first][u.div2+1]});
                }
            }
        }
    }

    double ans = (double)(1e15);
    for(int i=0;i<=K;i++) ans = min(ans, dp[H][i]);
    if(ans == (double)(1e15)) ans = -1;
    return ans;
}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    int check_sub_2_5 = 0;
    for(int i=0;i<N;i++) check_sub_2_5 += (arr[i] == 1);
    if(check_sub_2_5 == N) return sub_2_5(N,M,K,H,x,y,c,arr);

    int check_sub_3_6 = 0;
    for(int i=0;i<N;i++) check_sub_3_6 += (arr[i] != 2);
    if(check_sub_3_6 == N) return sub_3_6(N,M,K,H,x,y,c,arr);

    if(K <= 30) return sub_1_4_7(N,M,K,H,x,y,c,arr);

    return sub_8(N,M,min(K,60),H,x,y,c,arr);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 468 KB Correct.
2 Correct 23 ms 440 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Correct.
2 Correct 26 ms 460 KB Correct.
3 Correct 24 ms 468 KB Correct.
4 Correct 31 ms 364 KB Correct.
5 Correct 25 ms 456 KB Correct.
6 Correct 20 ms 1508 KB Correct.
7 Correct 29 ms 1448 KB Correct.
8 Correct 11 ms 2656 KB Correct.
9 Correct 26 ms 340 KB Correct.
10 Correct 24 ms 368 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 432 KB Correct.
2 Correct 27 ms 432 KB Correct.
3 Correct 24 ms 456 KB Correct.
4 Correct 27 ms 380 KB Correct.
5 Correct 28 ms 340 KB Correct.
6 Correct 6 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 27280 KB Correct.
2 Correct 270 ms 1096 KB Correct.
3 Correct 236 ms 1120 KB Correct.
4 Correct 255 ms 1024 KB Correct.
5 Correct 199 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 500 KB Correct.
2 Correct 25 ms 472 KB Correct.
3 Correct 24 ms 448 KB Correct.
4 Correct 23 ms 1412 KB Correct.
5 Correct 21 ms 388 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 468 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 40 ms 8964 KB Correct.
4 Correct 15 ms 1200 KB Correct.
5 Correct 25 ms 388 KB Correct.
6 Correct 23 ms 468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 1536 KB Correct.
2 Correct 41 ms 2312 KB Correct.
3 Correct 839 ms 29764 KB Correct.
4 Correct 547 ms 7892 KB Correct.
5 Correct 1613 ms 50024 KB Correct.
6 Correct 735 ms 41216 KB Correct.
7 Correct 508 ms 8176 KB Correct.
8 Correct 504 ms 1788 KB Correct.
9 Correct 243 ms 2084 KB Correct.
10 Correct 259 ms 1500 KB Correct.
11 Correct 478 ms 908 KB Correct.
12 Correct 253 ms 1676 KB Correct.
13 Correct 280 ms 1692 KB Correct.
14 Correct 496 ms 10996 KB Correct.
15 Correct 487 ms 3356 KB Correct.
16 Correct 254 ms 1552 KB Correct.
17 Correct 294 ms 1596 KB Correct.
18 Correct 300 ms 1524 KB Correct.
19 Correct 714 ms 1704 KB Correct.
20 Correct 19 ms 724 KB Correct.
21 Correct 20 ms 1052 KB Correct.
22 Correct 37 ms 3272 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 4100 KB Correct.
2 Correct 112 ms 7108 KB Correct.
3 Incorrect 555 ms 62880 KB Wrong Answer.
4 Halted 0 ms 0 KB -