oj.uz

Submission #751177

# Submission time Handle Problem Language Result Execution time Memory
751177 2023-05-31T07:19:32 Z Hona_Nguyen Cyberland (APIO23_cyberland) C++17
97 / 100
 1332 ms 137352 KB 
#include "cyberland.h"

#include <bits/stdc++.h>
#pragma GCC optimize "Ofast"
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<int>> vis_go(N, vector<int> (K+2, 0));
    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]});
    vis_go[0][0] = 1;

    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;
            vis_go[i][0] = 1;
            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] && vis_go[v.first][u.div2+1] < 70){
                dp[v.first][u.div2] = dp[u.id][u.div2] + v.second;
                vis_go[v.first][u.div2]++;
                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] && vis_go[v.first][u.div2+1] < 70){
                    dp[v.first][u.div2+1] = tmp;
                    vis_go[v.first][u.div2+1]++;
                    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,100),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 468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 444 KB Correct.
2 Correct 28 ms 408 KB Correct.
3 Correct 27 ms 452 KB Correct.
4 Correct 25 ms 472 KB Correct.
5 Correct 27 ms 448 KB Correct.
6 Correct 25 ms 1532 KB Correct.
7 Correct 28 ms 1432 KB Correct.
8 Correct 12 ms 2644 KB Correct.
9 Correct 26 ms 384 KB Correct.
10 Correct 25 ms 392 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 460 KB Correct.
2 Correct 27 ms 456 KB Correct.
3 Correct 26 ms 608 KB Correct.
4 Correct 31 ms 388 KB Correct.
5 Correct 26 ms 384 KB Correct.
6 Correct 6 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 27252 KB Correct.
2 Correct 299 ms 1068 KB Correct.
3 Correct 269 ms 1132 KB Correct.
4 Correct 274 ms 1076 KB Correct.
5 Correct 233 ms 484 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 496 KB Correct.
2 Correct 27 ms 468 KB Correct.
3 Correct 25 ms 468 KB Correct.
4 Correct 24 ms 1492 KB Correct.
5 Correct 22 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 22 ms 468 KB Correct.
3 Correct 40 ms 9064 KB Correct.
4 Correct 16 ms 1200 KB Correct.
5 Correct 26 ms 396 KB Correct.
6 Correct 24 ms 484 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 1568 KB Correct.
2 Correct 43 ms 2360 KB Correct.
3 Correct 723 ms 29772 KB Correct.
4 Correct 537 ms 7880 KB Correct.
5 Correct 1166 ms 49960 KB Correct.
6 Correct 531 ms 41264 KB Correct.
7 Correct 524 ms 8200 KB Correct.
8 Correct 520 ms 1696 KB Correct.
9 Correct 261 ms 2188 KB Correct.
10 Correct 260 ms 1556 KB Correct.
11 Correct 523 ms 960 KB Correct.
12 Correct 278 ms 1920 KB Correct.
13 Correct 297 ms 1600 KB Correct.
14 Correct 460 ms 10860 KB Correct.
15 Correct 505 ms 3428 KB Correct.
16 Correct 276 ms 1532 KB Correct.
17 Correct 315 ms 1484 KB Correct.
18 Correct 335 ms 1472 KB Correct.
19 Correct 765 ms 1624 KB Correct.
20 Correct 23 ms 724 KB Correct.
21 Correct 21 ms 992 KB Correct.
22 Correct 35 ms 3336 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 5408 KB Correct.
2 Correct 178 ms 8996 KB Correct.
3 Correct 905 ms 137352 KB Correct.
4 Incorrect 1234 ms 8888 KB Wrong Answer.
5 Halted 0 ms 0 KB -