oj.uz

답안 #750999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750999 2023-05-30T18:21:32 Z Hona_Nguyen 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 3000 ms 159772 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,70),H,x,y,c,arr);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 460 KB Correct.
2 Correct 24 ms 372 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 480 KB Correct.
2 Correct 28 ms 436 KB Correct.
3 Correct 26 ms 468 KB Correct.
4 Correct 28 ms 548 KB Correct.
5 Correct 27 ms 468 KB Correct.
6 Correct 22 ms 1500 KB Correct.
7 Correct 27 ms 1432 KB Correct.
8 Correct 12 ms 2644 KB Correct.
9 Correct 26 ms 392 KB Correct.
10 Correct 25 ms 392 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 460 KB Correct.
2 Correct 27 ms 468 KB Correct.
3 Correct 30 ms 468 KB Correct.
4 Correct 29 ms 376 KB Correct.
5 Correct 29 ms 340 KB Correct.
6 Correct 6 ms 1364 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 27340 KB Correct.
2 Correct 294 ms 1284 KB Correct.
3 Correct 235 ms 1260 KB Correct.
4 Correct 252 ms 1132 KB Correct.
5 Correct 200 ms 516 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 468 KB Correct.
2 Correct 24 ms 380 KB Correct.
3 Correct 23 ms 468 KB Correct.
4 Correct 22 ms 1404 KB Correct.
5 Correct 22 ms 372 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 460 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 42 ms 9068 KB Correct.
4 Correct 16 ms 1248 KB Correct.
5 Correct 27 ms 384 KB Correct.
6 Correct 24 ms 504 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 289 ms 1472 KB Correct.
2 Correct 45 ms 2360 KB Correct.
3 Correct 796 ms 29868 KB Correct.
4 Correct 547 ms 7976 KB Correct.
5 Correct 1692 ms 50200 KB Correct.
6 Correct 756 ms 41220 KB Correct.
7 Correct 526 ms 8136 KB Correct.
8 Correct 488 ms 1920 KB Correct.
9 Correct 243 ms 2104 KB Correct.
10 Correct 252 ms 1520 KB Correct.
11 Correct 479 ms 924 KB Correct.
12 Correct 261 ms 1748 KB Correct.
13 Correct 272 ms 1632 KB Correct.
14 Correct 470 ms 10884 KB Correct.
15 Correct 492 ms 3372 KB Correct.
16 Correct 256 ms 1576 KB Correct.
17 Correct 288 ms 1508 KB Correct.
18 Correct 291 ms 1480 KB Correct.
19 Correct 700 ms 1556 KB Correct.
20 Correct 18 ms 724 KB Correct.
21 Correct 20 ms 1060 KB Correct.
22 Correct 39 ms 3272 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 928 ms 4668 KB Correct.
2 Correct 127 ms 7560 KB Correct.
3 Correct 591 ms 70868 KB Correct.
4 Correct 1083 ms 5052 KB Correct.
5 Execution timed out 3068 ms 159772 KB Time limit exceeded
6 Halted 0 ms 0 KB -