oj.uz

Submission #755053

# Submission time Handle Problem Language Result Execution time Memory
755053 2023-06-09T11:06:06 Z ttamx Cyberland (APIO23_cyberland) C++17
100 / 100
 2955 ms 142972 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

typedef double db;
typedef tuple<db,int,int,bool> t4;

const int N=1e5+5;
const int K=75;

int n,m,k,h;
int a[N];
db dp[N][K][2];
bool vis[N][K][2];
vector<pair<int,db>> adj[N];
priority_queue<t4,vector<t4>,greater<t4>> pq;

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=min(K,70),h=H;
    for(int i=0;i<n;i++)adj[i].clear();
    for(int i=0;i<m;i++){
        int u=x[i],v=y[i],w=c[i];
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    for(int i=0;i<n;i++)a[i]=arr[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i][j][1]=DBL_MAX;
            vis[i][j][0]=vis[i][j][1]=false;
        }
    }
    while(!pq.empty())pq.pop();
    pq.emplace(0,h,0,0);
    for(int i=0;i<=k;i++)dp[h][i][0]=dp[h][i][1]=0;
    while(!pq.empty()){
        auto [d,u,s,f]=pq.top();
        pq.pop();
        if(vis[u][s][f])continue;
        vis[u][s][f]=true;
        for(auto [v,w]:adj[u]){
            db res=d+(f?0:w/pow(2.0,s));
            if(res>=dp[v][s][f])continue;
            dp[v][s][f]=res;
            pq.emplace(res,v,s,f);
        }
        if(a[u]==0&&f==0){
            for(auto [v,w]:adj[u]){
                db res=d;
                if(res>=dp[v][s][1])continue;
                dp[v][s][1]=res;
                pq.emplace(res,v,s,1);
            }
        }
        if(a[u]==2&&s<k){
            for(auto [v,w]:adj[u]){
                db res=d+(f?0:w/pow(2.0,s+1));
                if(res>=dp[v][s+1][f])continue;
                dp[v][s+1][f]=res;
                pq.emplace(res,v,s+1,f);
            }
        }
    }
    db ans=DBL_MAX;
    for(int i=0;i<=k;i++)ans=min({ans,dp[0][i][0],dp[0][i][1]});
    if(ans==DBL_MAX)ans=-1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2832 KB Correct.
2 Correct 25 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4180 KB Correct.
2 Correct 30 ms 4180 KB Correct.
3 Correct 33 ms 4176 KB Correct.
4 Correct 30 ms 4156 KB Correct.
5 Correct 30 ms 4152 KB Correct.
6 Correct 37 ms 16508 KB Correct.
7 Correct 43 ms 16216 KB Correct.
8 Correct 28 ms 30296 KB Correct.
9 Correct 28 ms 2876 KB Correct.
10 Correct 28 ms 2864 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4128 KB Correct.
2 Correct 34 ms 4180 KB Correct.
3 Correct 34 ms 4128 KB Correct.
4 Correct 40 ms 2872 KB Correct.
5 Correct 33 ms 2876 KB Correct.
6 Correct 15 ms 14112 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 84392 KB Correct.
2 Correct 359 ms 4136 KB Correct.
3 Correct 351 ms 4168 KB Correct.
4 Correct 330 ms 4044 KB Correct.
5 Correct 348 ms 2988 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4180 KB Correct.
2 Correct 31 ms 4208 KB Correct.
3 Correct 33 ms 4180 KB Correct.
4 Correct 39 ms 16852 KB Correct.
5 Correct 24 ms 2884 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4240 KB Correct.
2 Correct 27 ms 4180 KB Correct.
3 Correct 87 ms 109260 KB Correct.
4 Correct 29 ms 12800 KB Correct.
5 Correct 38 ms 2864 KB Correct.
6 Correct 41 ms 4284 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 4404 KB Correct.
2 Correct 59 ms 5552 KB Correct.
3 Correct 1216 ms 136536 KB Correct.
4 Correct 647 ms 33356 KB Correct.
5 Correct 1217 ms 68448 KB Correct.
6 Correct 560 ms 28216 KB Correct.
7 Correct 664 ms 36108 KB Correct.
8 Correct 547 ms 7628 KB Correct.
9 Correct 292 ms 4492 KB Correct.
10 Correct 301 ms 4468 KB Correct.
11 Correct 522 ms 4600 KB Correct.
12 Correct 337 ms 4332 KB Correct.
13 Correct 307 ms 4404 KB Correct.
14 Correct 656 ms 68064 KB Correct.
15 Correct 642 ms 20452 KB Correct.
16 Correct 301 ms 4372 KB Correct.
17 Correct 362 ms 4416 KB Correct.
18 Correct 294 ms 4404 KB Correct.
19 Correct 833 ms 4340 KB Correct.
20 Correct 24 ms 2772 KB Correct.
21 Correct 25 ms 4292 KB Correct.
22 Correct 40 ms 5324 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 4676 KB Correct.
2 Correct 138 ms 5832 KB Correct.
3 Correct 1528 ms 142972 KB Correct.
4 Correct 760 ms 11764 KB Correct.
5 Correct 2618 ms 105408 KB Correct.
6 Correct 1296 ms 46712 KB Correct.
7 Correct 1293 ms 53244 KB Correct.
8 Correct 813 ms 4840 KB Correct.
9 Correct 650 ms 4572 KB Correct.
10 Correct 614 ms 4676 KB Correct.
11 Correct 467 ms 2932 KB Correct.
12 Correct 790 ms 4616 KB Correct.
13 Correct 741 ms 4732 KB Correct.
14 Correct 2955 ms 58556 KB Correct.
15 Correct 2695 ms 72264 KB Correct.
16 Correct 1123 ms 28096 KB Correct.
17 Correct 804 ms 7880 KB Correct.
18 Correct 704 ms 4592 KB Correct.
19 Correct 803 ms 4724 KB Correct.
20 Correct 677 ms 4656 KB Correct.
21 Correct 1870 ms 4508 KB Correct.
22 Correct 63 ms 2900 KB Correct.
23 Correct 55 ms 4436 KB Correct.
24 Correct 83 ms 6096 KB Correct.