oj.uz

Submission #751179

# Submission time Handle Problem Language Result Execution time Memory
751179 2023-05-31T07:20:28 Z Hona_Nguyen Cyberland (APIO23_cyberland) C++17
97 / 100
 1495 ms 137348 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] < K){
                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] < K){
                    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 25 ms 456 KB Correct.
2 Correct 23 ms 368 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 484 KB Correct.
2 Correct 27 ms 468 KB Correct.
3 Correct 25 ms 428 KB Correct.
4 Correct 31 ms 436 KB Correct.
5 Correct 31 ms 444 KB Correct.
6 Correct 24 ms 1504 KB Correct.
7 Correct 33 ms 1432 KB Correct.
8 Correct 12 ms 2660 KB Correct.
9 Correct 25 ms 388 KB Correct.
10 Correct 27 ms 388 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 456 KB Correct.
2 Correct 27 ms 480 KB Correct.
3 Correct 26 ms 504 KB Correct.
4 Correct 28 ms 380 KB Correct.
5 Correct 27 ms 340 KB Correct.
6 Correct 7 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 27240 KB Correct.
2 Correct 295 ms 1088 KB Correct.
3 Correct 267 ms 1208 KB Correct.
4 Correct 281 ms 1196 KB Correct.
5 Correct 230 ms 484 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 460 KB Correct.
2 Correct 27 ms 468 KB Correct.
3 Correct 25 ms 608 KB Correct.
4 Correct 24 ms 1492 KB Correct.
5 Correct 22 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 484 KB Correct.
2 Correct 22 ms 468 KB Correct.
3 Correct 51 ms 8944 KB Correct.
4 Correct 17 ms 1280 KB Correct.
5 Correct 26 ms 392 KB Correct.
6 Correct 24 ms 508 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 1592 KB Correct.
2 Correct 41 ms 2364 KB Correct.
3 Correct 805 ms 29748 KB Correct.
4 Correct 580 ms 7876 KB Correct.
5 Correct 1296 ms 50060 KB Correct.
6 Correct 545 ms 41376 KB Correct.
7 Correct 539 ms 8136 KB Correct.
8 Correct 576 ms 2024 KB Correct.
9 Correct 279 ms 2176 KB Correct.
10 Correct 273 ms 1612 KB Correct.
11 Correct 528 ms 976 KB Correct.
12 Correct 303 ms 1588 KB Correct.
13 Correct 306 ms 1592 KB Correct.
14 Correct 458 ms 10992 KB Correct.
15 Correct 545 ms 3348 KB Correct.
16 Correct 284 ms 1592 KB Correct.
17 Correct 330 ms 1504 KB Correct.
18 Correct 342 ms 1492 KB Correct.
19 Correct 806 ms 1768 KB Correct.
20 Correct 22 ms 724 KB Correct.
21 Correct 22 ms 1076 KB Correct.
22 Correct 44 ms 3324 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 7440 KB Correct.
2 Correct 187 ms 9008 KB Correct.
3 Correct 938 ms 137348 KB Correct.
4 Incorrect 1343 ms 8980 KB Wrong Answer.
5 Halted 0 ms 0 KB -