Submission #982496

#TimeUsernameProblemLanguageResultExecution timeMemory
982496ASGA_RedSeaCyberland (APIO23_cyberland)C++17
0 / 100
25 ms7144 KiB
/** * بسم الله الرحمن الرحيم * ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿ */ /// author : "ASGA" #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; 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; } void calc(int i,int ck){ for(auto& j : g[i]){ if(a[j.b] == 0){ if(d[j.b] <= err)continue; d[j.b] = 0.00000000000; if(j.b != h)calc(j.b,ck); } 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(j.b != h)calc(j.b,ck + 1); } } if((d[j.b] - (d[i] + j.c)) <= err)continue; d[j.b] = (d[i] + j.c); if(j.b != h)calc(j.b,ck); } } } 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); d[0] = 0; calc(0,0); return d[h]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...