Submission #982506

#	Time	Username	Problem	Language	Result	Execution time	Memory
982506		ASGA_RedSea	Cyberland (APIO23_cyberland)	C++17	0 / 100	24 ms	6196 KiB

cyberland

/**

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

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

*/

/// 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;

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);
    }

    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 (abs(d[h] - inf) <= err ? -1 : d[h]);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3