oj.uz

Submission #982504

# Submission time Handle Problem Language Result Execution time Memory
982504 2024-05-14T10:22:04 Z ASGA_RedSea Cyberland (APIO23_cyberland) C++17
0 / 100
 22 ms 6748 KB 
/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;


const double inf = 1e18;
const double err = 1e-7;

struct w{
    int b,c;
};

w hi;
int n,m,k,h;
vector <int> a,v;
vector <double> d;
vector <vector <w>> g;
priority_queue <pair <double,pair <int,int>>> q;

bool check(int i){
    v[i] = 1;
    for(auto& j : g[i]){
        if(v[j.b])continue;
        if(j.b == h || check(j.b))return 1;
    }
    return 0;
}

double solve(int N,int M,int K,int H,vector <int> X,vector <int> Y,vector <int> C,vector <int> A){
    n = N;m = M;k = K;h = H;a = A;

    g.resize(n);
    for(int i = 0;i < m;i++){
        hi.b = Y[i];
        hi.c = C[i];
        g[X[i]].push_back(hi);
        hi.b = X[i];
        g[Y[i]].push_back(hi);
    }

    v = vector <int> (n,0);
    if(check(0) == 0)return -1;

    d = vector <double> (n,inf);
    v = vector <int> (n,0);
    d[0] = 0;
    q.push({0,{0,0}});

    while(!q.empty()){
        pair <double,pair <int,int>> s = q.top();q.pop();

        int i = s.second.second,ck = s.second.first;

        for(auto& j : g[i]){
            if(a[j.b] == 0){
                if(d[j.b] <= err)continue;
                d[j.b] = 0.00000000000;
                if(v[j.b] == 0 && j.b != h){q.push({0.00000000,{ck,j.b}});v[j.b]++;}
            }
            else{
                if(a[j.b] == 2 && ck < k){
                    if(d[j.b] - ((d[i] + j.c) / 2.0000000) > err){
                        d[j.b] = ((d[i] + j.c) / 2.00000000);
                        if(v[j.b] == 0 && j.b != h){q.push({-d[j.b],{ck + 1,j.b}});v[j.b]++;}
                    }
                }

                if((d[j.b] - (d[i] + j.c)) <= err)continue;
                d[j.b] = (d[i] + j.c);
                if(v[j.b] == 0 && j.b != h){q.push({-d[j.b],{ck,j.b}});v[j.b]++;}
            }
        }
    }

    return d[h];
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -