oj.uz

Submission #976692

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



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 long dis2[N][min(K,41)+1];
    long double dis[N][min(K,41)+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 long,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;
                long long 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<long long,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 long d=mn.first;
        long double d2=mn.second;
        if(d>INF)return d;
        else{
            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 17 ms 600 KB Correct.
2 Correct 17 ms 812 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1372 KB Correct.
2 Correct 28 ms 2392 KB Correct.
3 Correct 27 ms 2140 KB Correct.
4 Correct 28 ms 2140 KB Correct.
5 Correct 27 ms 2136 KB Correct.
6 Correct 26 ms 9296 KB Correct.
7 Correct 35 ms 9496 KB Correct.
8 Correct 26 ms 17212 KB Correct.
9 Correct 24 ms 1308 KB Correct.
10 Correct 24 ms 1364 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1112 KB Correct.
2 Correct 24 ms 2248 KB Correct.
3 Correct 23 ms 2180 KB Correct.
4 Correct 24 ms 1368 KB Correct.
5 Correct 24 ms 1368 KB Correct.
6 Correct 7 ms 7004 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47696 KB Correct.
2 Correct 24 ms 2140 KB Correct.
3 Correct 21 ms 2140 KB Correct.
4 Correct 22 ms 2148 KB Correct.
5 Correct 35 ms 1368 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1368 KB Correct.
2 Correct 41 ms 2484 KB Correct.
3 Correct 31 ms 2416 KB Correct.
4 Correct 40 ms 10500 KB Correct.
5 Correct 25 ms 1372 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1340 KB Correct.
2 Correct 22 ms 2140 KB Correct.
3 Correct 63 ms 64212 KB Correct.
4 Correct 18 ms 6648 KB Correct.
5 Correct 26 ms 1320 KB Correct.
6 Correct 28 ms 2140 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 1820 KB Correct.
2 Correct 43 ms 2136 KB Correct.
3 Correct 1113 ms 52136 KB Correct.
4 Correct 483 ms 15884 KB Correct.
5 Correct 995 ms 38040 KB Correct.
6 Correct 873 ms 21420 KB Correct.
7 Correct 573 ms 15456 KB Correct.
8 Correct 303 ms 4756 KB Correct.
9 Correct 194 ms 2432 KB Correct.
10 Correct 182 ms 2828 KB Correct.
11 Correct 226 ms 3152 KB Correct.
12 Correct 200 ms 2700 KB Correct.
13 Correct 199 ms 2460 KB Correct.
14 Correct 558 ms 14676 KB Correct.
15 Correct 536 ms 7504 KB Correct.
16 Correct 219 ms 2464 KB Correct.
17 Correct 196 ms 2644 KB Correct.
18 Correct 188 ms 2432 KB Correct.
19 Correct 178 ms 3056 KB Correct.
20 Correct 16 ms 600 KB Correct.
21 Correct 17 ms 1116 KB Correct.
22 Correct 78 ms 2392 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 1960 KB Correct.
2 Correct 63 ms 2700 KB Correct.
3 Incorrect 1181 ms 110420 KB Double -23278.5 violates the range [-1, 1e+18]
4 Halted 0 ms 0 KB -