| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 783576 | vjudge1 | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
constexpr int N=1e5+5,KX=70
constexpr double INF=1e99;
int n,m,kk,h,ty[N];
vector<pii> g[N];
bool reach[N];
double f[N][KX+3][2];
vector<int> st;
inline void bfsinit(int s){
queue<int> q;
memset(reach,0,n*sizeof(bool));
reach[s]=true,
q.emplace(s);
while(!q.empty()){
int u{q.front()};q.pop();
for(auto e:g[u]){
int v{e.first};
if(!reach[v]){
reach[v]=true,
q.emplace(v);
}
}
}
}
inline void dijx(){
struct Q{
int u,d;
double dis;
bool div2;
Q(){}
Q(int u,int d,double ds,bool d2):
u{u},d{d},dis{ds},div2{d2}{}
inline bool operator<(const Q &b)const{
return dis>b.dis;
}
};
queue<Q> q;
static bool inq[N][KX+3][2];
for(int i{0};i<n;++i){
for(int j{0};j<=kk;++j){
f[i][j][0]=f[i][j][1]=INF;
inq[i][j][0]=inq[i][j][1]=false;
}
}
for(int s:st){
f[s][0][0]=0.0;
q.emplace(s,0,f[s][0][0],false);
inq[s][0][0]=true;
}
while(!q.empty()){
auto t=q.front();q.pop();
inq[t.u][t.d][t.div2]=false;
double tdis=f[t.u][t.d][t.div2];
if(t.d<kk&&!t.div2&&ty[t.u]==2&&tdis/2.0<f[t.u][t.d+1][1]){
f[t.u][t.d+1][1]=tdis/2.0;
if(!inq[t.u][t.d+1][1]){
q.emplace(t.u,t.d+1,f[t.u][t.d+1][1],true);
inq[t.u][t.d+1][1]=true;
}
}
for(pii e:g[t.u]){
int v{e.first},w{e.second};
if(tdis+w<f[v][t.d][0]){
f[v][t.d][0]=tdis+w;
if(!inq[v][t.d][0]){
q.emplace(v,t.d,f[v][t.d][0],false);
inq[v][t.d][0]=true;
}
}
}
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
n=N,m=M,kk=K,h=H;
kk=min(kk,KX);
for(int i{0};i<n;++i){
ty[i]=arr[i];
g[i].clear();
}
for(int i{0};i<m;++i){
int u{x[i]},v{y[i]},w{c[i]};
if(u!=h) g[u].emplace_back(v,w);
if(v!=h) g[v].emplace_back(u,w);
}
bfsinit(0);
if(!reach[h]) return -1;
for(int i{0};i<n;++i){
if(i==0||(ty[i]==0&&reach[i])){
st.emplace_back(i);
}
}
dijx();
double ans{INF};
for(int i{0};i<=kk;++i){
ans=min({ans,f[h][i][0],f[h][i][1]});
}
st.clear();
return ans;
}