oj.uz

Submission #976696

# Submission time Handle Problem Language Result Execution time Memory
976696 2024-05-07T03:15:29 Z Mr_Husanboy Cyberland (APIO23_cyberland) C++17
97 / 100
 1415 ms 80756 KB 
#include "bits/stdc++.h"
#include "cyberland.h"
using namespace std;
#define INF 2000000000
#define INFLL 3000000000000000000LL
#define ll long double


double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<pair<int,int>>adj[N];
    for(int i=0;i<M;i++){
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    long double dis2[N][min(K,40)+1];
    long double dis[N][min(K,40)+1];
    for(int i=0;i<N;i++){
        for(int j=0;j<=min(K,41);j++){
            dis2[i][j]=INFLL;
            dis[i][j]=0;
        }
    }
    priority_queue<pair<pair<long double,long double>,pair<int,int>>>q;
    q.push({{-0,-0},{H,0}});
    while(!q.empty()){
        auto u=q.top();q.pop();
        long long d1=-u.first.first;
        long double d=-u.first.second;
        int cur=u.second.first;
        int k=u.second.second;
        //cout<<dis[cur][k]<<" ";
        if(dis2[cur][k]!=INFLL)continue;
        //cout<<dis[cur][k]<<" ";
        dis2[cur][k]=d1;
        dis[cur][k]=d;
        if(arr[cur]==2)k=min(min(K,41),k+1);
        if(arr[cur]!=0&&cur!=0){
            long double fact1=1<<k;
            long double fact2=1<<max(k-30,0);
            for(auto v:adj[cur]){
                if(v.first==H)continue;
                long double qw=d+v.second/fact1/fact2;
                //cout<<qw<<" ";
                int qwe=qw;
                long double d2=qw-qwe;
                ll d3=d1+qwe;
                q.push({{-d3,-d2},{v.first,k}});
            }
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<=min(K,41);j++){
            long double d=dis2[i][j];
            d+=dis[i][j];
            //cout<<d<<" ";
        }
        //cout<<"\n";
    }
    queue<int>q2;
    vector<bool>vis(N,0);
    q2.push(0);
    pair<ll,long double>mn={INFLL,0};
    for(int i=0;i<=min(K,41);i++)mn=min(mn,{dis2[0][i],dis[0][i]});
    while(!q2.empty()){
        int cur=q2.front();
        q2.pop();
        if(vis[cur]||cur==H)continue;
        vis[cur]=1;
        if(arr[cur]==0)for(int i=0;i<=min(K,41);i++)mn=min(mn,{dis2[cur][i],dis[cur][i]});
        for(auto u:adj[cur])q2.push(u.first);
    }
    if(mn.first==INFLL){
        return -1;
    }
    else{
        long double d2=mn.second;
        long double ret=mn.first;
        ret+=d2;
        return ret;
    }
    
    
    
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Correct.
2 Correct 21 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1372 KB Correct.
2 Correct 38 ms 1620 KB Correct.
3 Correct 36 ms 1368 KB Correct.
4 Correct 36 ms 1372 KB Correct.
5 Correct 36 ms 1368 KB Correct.
6 Correct 34 ms 10840 KB Correct.
7 Correct 45 ms 10800 KB Correct.
8 Correct 32 ms 21496 KB Correct.
9 Correct 32 ms 600 KB Correct.
10 Correct 32 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1488 KB Correct.
2 Correct 36 ms 1504 KB Correct.
3 Correct 38 ms 1504 KB Correct.
4 Correct 32 ms 604 KB Correct.
5 Correct 32 ms 588 KB Correct.
6 Correct 10 ms 8752 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 61972 KB Correct.
2 Correct 33 ms 1784 KB Correct.
3 Correct 28 ms 1368 KB Correct.
4 Correct 29 ms 1372 KB Correct.
5 Correct 47 ms 600 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1532 KB Correct.
2 Correct 44 ms 1628 KB Correct.
3 Correct 51 ms 1820 KB Correct.
4 Correct 51 ms 11736 KB Correct.
5 Correct 33 ms 600 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1368 KB Correct.
2 Correct 30 ms 1372 KB Correct.
3 Correct 82 ms 80756 KB Correct.
4 Correct 25 ms 7668 KB Correct.
5 Correct 31 ms 348 KB Correct.
6 Correct 32 ms 1372 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 2060 KB Correct.
2 Correct 64 ms 2640 KB Correct.
3 Correct 1415 ms 63004 KB Correct.
4 Correct 746 ms 17328 KB Correct.
5 Correct 1296 ms 43416 KB Correct.
6 Correct 1261 ms 21184 KB Correct.
7 Correct 781 ms 16864 KB Correct.
8 Correct 425 ms 3360 KB Correct.
9 Correct 288 ms 1908 KB Correct.
10 Correct 267 ms 2020 KB Correct.
11 Correct 327 ms 1660 KB Correct.
12 Correct 263 ms 1852 KB Correct.
13 Correct 293 ms 1848 KB Correct.
14 Correct 811 ms 15228 KB Correct.
15 Correct 794 ms 6684 KB Correct.
16 Correct 297 ms 1936 KB Correct.
17 Correct 282 ms 1744 KB Correct.
18 Correct 269 ms 1820 KB Correct.
19 Correct 269 ms 1532 KB Correct.
20 Correct 32 ms 604 KB Correct.
21 Correct 23 ms 1624 KB Correct.
22 Correct 121 ms 2476 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 405 ms 2292 KB Wrong Answer.
2 Halted 0 ms 0 KB -