oj.uz

Submission #750997

# Submission time Handle Problem Language Result Execution time Memory
750997 2023-05-30T18:20:23 Z Hona_Nguyen Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 168076 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,100),H,x,y,c,arr);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 368 KB Correct.
2 Correct 22 ms 472 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 468 KB Correct.
2 Correct 35 ms 448 KB Correct.
3 Correct 34 ms 424 KB Correct.
4 Correct 26 ms 468 KB Correct.
5 Correct 26 ms 464 KB Correct.
6 Correct 22 ms 1504 KB Correct.
7 Correct 28 ms 1476 KB Correct.
8 Correct 13 ms 2644 KB Correct.
9 Correct 27 ms 392 KB Correct.
10 Correct 25 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 460 KB Correct.
2 Correct 26 ms 460 KB Correct.
3 Correct 26 ms 468 KB Correct.
4 Correct 28 ms 384 KB Correct.
5 Correct 29 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 278 ms 27272 KB Correct.
2 Correct 289 ms 1128 KB Correct.
3 Correct 243 ms 1180 KB Correct.
4 Correct 271 ms 1088 KB Correct.
5 Correct 218 ms 452 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 504 KB Correct.
2 Correct 26 ms 480 KB Correct.
3 Correct 25 ms 472 KB Correct.
4 Correct 24 ms 1492 KB Correct.
5 Correct 23 ms 384 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 488 KB Correct.
2 Correct 25 ms 520 KB Correct.
3 Correct 48 ms 9012 KB Correct.
4 Correct 16 ms 1200 KB Correct.
5 Correct 26 ms 396 KB Correct.
6 Correct 24 ms 388 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 1540 KB Correct.
2 Correct 42 ms 2364 KB Correct.
3 Correct 885 ms 29840 KB Correct.
4 Correct 602 ms 8016 KB Correct.
5 Correct 1699 ms 49956 KB Correct.
6 Correct 724 ms 41236 KB Correct.
7 Correct 537 ms 8200 KB Correct.
8 Correct 509 ms 1676 KB Correct.
9 Correct 246 ms 2120 KB Correct.
10 Correct 248 ms 1540 KB Correct.
11 Correct 502 ms 968 KB Correct.
12 Correct 256 ms 1620 KB Correct.
13 Correct 288 ms 1684 KB Correct.
14 Correct 504 ms 10984 KB Correct.
15 Correct 501 ms 3392 KB Correct.
16 Correct 249 ms 1712 KB Correct.
17 Correct 325 ms 1568 KB Correct.
18 Correct 320 ms 1500 KB Correct.
19 Correct 727 ms 1632 KB Correct.
20 Correct 19 ms 744 KB Correct.
21 Correct 20 ms 1048 KB Correct.
22 Correct 38 ms 3272 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1418 ms 7300 KB Correct.
2 Correct 189 ms 8756 KB Correct.
3 Correct 856 ms 94284 KB Correct.
4 Correct 1436 ms 7340 KB Correct.
5 Execution timed out 3061 ms 168076 KB Time limit exceeded
6 Halted 0 ms 0 KB -