oj.uz

Submission #756672

# Submission time Handle Problem Language Result Execution time Memory
756672 2023-06-12T04:22:15 Z ByeWorld Cyberland (APIO23_cyberland) C++17
100 / 100
 2422 ms 92424 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5+10;
const int MAXK = 105;
const double INF = 1e16+10;
const ll MOD = 1e9 + 7;
const ll LOG = 20;
typedef pair<int,int> pii;
typedef pair<int,double> piii;
typedef pair<double, int> ipii;

int n, m, k, h;
double dp[MAXK][MAXN];
vector <pii> adj[MAXN];
priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
//priority_queue <ipii> pq;
bool vis[MAXN];
vector <piii> en;

void reset(){
    en.clear();
    for(int i=0; i<n; i++){
        adj[i].clear();
        vis[i] = 0;
    }
}
void dfs(int nw){
    if(vis[nw]) return;
    vis[nw] = 1;
    for(auto nx : adj[nw]){ 
        dfs(nx.fi);
    }
}
void dji(int idx){
    for(int i=0; i<n; i++) pq.push(ipii(dp[idx][i], i));
    while(!pq.empty()){
        double dis = pq.top().fi; int nw = pq.top().se; pq.pop();
        if(dis > dp[idx][nw]) continue;
        for(auto ed : adj[nw]){
            int nx = ed.fi; double wei = ed.se;
            if(dp[idx][nx] > dp[idx][nw] + wei){
                dp[idx][nx] = dp[idx][nw] + wei;
                pq.push(ipii(dp[idx][nx], nx));
            } 
        }
    }
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n = N; m = M; k = K; h = H; k = min(k, 100);
    reset();
    for(int i=0; i<=m-1; i++){
        if(x[i] == h) en.pb(pii(y[i], c[i]));
        else if(y[i] == h) en.pb(pii(x[i], c[i]));
        else {
            adj[x[i]].pb(pii(y[i], c[i])); adj[y[i]].pb(pii(x[i], c[i]));
        }
    }
    dfs(0);
    // step 1
    for(int i=0; i<n; i++){ //idx = sta-en
        for(int j=0; j<=k; j++) dp[j][i] = INF;
    }
    for(int i=0; i<n; i++) {
        if(vis[i] && arr[i] == 0) dp[0][i] = 0;
    }
    dp[0][0] = 0;
    /*for(auto in : vec)cout << in.fi << ' ' << in.se << "in\n";
    cout << sta << ' ' << en << "sta\n";
    return 0;*/
    //dji(0);
    for(int j=0; j<=k; j++){
        // step 3
        if(j!=0){
            for(int i=0; i<n; i++){
                if(!vis[i] || arr[i]!=2) continue;
                for(auto ed : adj[i]){
                    int nx = ed.fi; int wei = ed.se;
                    dp[j][i] = min(dp[j][i], (dp[j-1][nx]+wei)/2);
                }
            }
        }
        // step 4
        dji(j);
        
        // for(int i=1; i<=h-1; i++){
        //     dp[j][i] = min(dp[j][i], dp[j][i-1]+c[i-1]);
        // }
        // for(int i=h-2; i>=0; i--){
        //     dp[j][i] = min(dp[j][i], dp[j][i+1]+c[i]);
        // }
    }
    /*for(int i=sta; i<=en; i++){
        for(int j=0; j<=k; j++) cout << dp[i][j] << ' ';
        cout << '\n';
    }*/
    // step 5
    double ans = INF;
    for(int i=0; i<=k; i++){
        for(auto in : en) ans = min(ans, dp[i][in.fi]+in.se);
    }
    if(ans==INF) return -1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2900 KB Correct.
2 Correct 41 ms 2916 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3252 KB Correct.
2 Correct 127 ms 3360 KB Correct.
3 Correct 131 ms 3180 KB Correct.
4 Correct 130 ms 3192 KB Correct.
5 Correct 129 ms 3196 KB Correct.
6 Correct 146 ms 6064 KB Correct.
7 Correct 218 ms 5972 KB Correct.
8 Correct 107 ms 9560 KB Correct.
9 Correct 94 ms 2904 KB Correct.
10 Correct 92 ms 2884 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3392 KB Correct.
2 Correct 151 ms 3208 KB Correct.
3 Correct 115 ms 3256 KB Correct.
4 Correct 112 ms 2876 KB Correct.
5 Correct 97 ms 2872 KB Correct.
6 Correct 32 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 22092 KB Correct.
2 Correct 264 ms 3236 KB Correct.
3 Correct 211 ms 3264 KB Correct.
4 Correct 222 ms 3172 KB Correct.
5 Correct 135 ms 2864 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 3180 KB Correct.
2 Correct 134 ms 3280 KB Correct.
3 Correct 124 ms 3216 KB Correct.
4 Correct 167 ms 6228 KB Correct.
5 Correct 95 ms 2880 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 3184 KB Correct.
2 Correct 106 ms 3284 KB Correct.
3 Correct 474 ms 28496 KB Correct.
4 Correct 124 ms 5244 KB Correct.
5 Correct 109 ms 2876 KB Correct.
6 Correct 116 ms 3180 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 3368 KB Correct.
2 Correct 33 ms 3412 KB Correct.
3 Correct 871 ms 24912 KB Correct.
4 Correct 451 ms 8832 KB Correct.
5 Correct 574 ms 17548 KB Correct.
6 Correct 185 ms 10056 KB Correct.
7 Correct 477 ms 8836 KB Correct.
8 Correct 379 ms 3988 KB Correct.
9 Correct 202 ms 3332 KB Correct.
10 Correct 215 ms 3220 KB Correct.
11 Correct 325 ms 3520 KB Correct.
12 Correct 239 ms 3240 KB Correct.
13 Correct 198 ms 3284 KB Correct.
14 Correct 518 ms 11280 KB Correct.
15 Correct 385 ms 5564 KB Correct.
16 Correct 221 ms 3196 KB Correct.
17 Correct 226 ms 3228 KB Correct.
18 Correct 223 ms 3284 KB Correct.
19 Correct 592 ms 3336 KB Correct.
20 Correct 15 ms 2772 KB Correct.
21 Correct 25 ms 3120 KB Correct.
22 Correct 21 ms 3616 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 4072 KB Correct.
2 Correct 76 ms 4708 KB Correct.
3 Correct 1959 ms 92424 KB Correct.
4 Correct 541 ms 7280 KB Correct.
5 Correct 1784 ms 37380 KB Correct.
6 Correct 579 ms 15956 KB Correct.
7 Correct 1050 ms 22240 KB Correct.
8 Correct 589 ms 4640 KB Correct.
9 Correct 540 ms 4116 KB Correct.
10 Correct 553 ms 4088 KB Correct.
11 Correct 201 ms 3404 KB Correct.
12 Correct 651 ms 4252 KB Correct.
13 Correct 551 ms 4288 KB Correct.
14 Correct 2422 ms 38672 KB Correct.
15 Correct 2416 ms 46500 KB Correct.
16 Correct 822 ms 14904 KB Correct.
17 Correct 615 ms 6380 KB Correct.
18 Correct 571 ms 4184 KB Correct.
19 Correct 639 ms 4088 KB Correct.
20 Correct 640 ms 4096 KB Correct.
21 Correct 1730 ms 4224 KB Correct.
22 Correct 29 ms 3252 KB Correct.
23 Correct 52 ms 3948 KB Correct.
24 Correct 52 ms 4452 KB Correct.