Submission #1194873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194873		dzuizz	사이버랜드 (APIO23_cyberland)	C++20	97 / 100	3099 ms	159320 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5,K=70;
constexpr double INF=DBL_MAX;
int n,m,k,h;
vector<pair<int,int>> g[N];
double di[N][K+1];
bool vi[N];
vector<int> v;
priority_queue<pair<double,pair<int,int>>> pq;  // (-d,i,j)
void find0(int u){
  vi[u]=1;
  for(auto&[w,v]:g[u]) if(!vi[v]&&v!=h)
    find0(v);
}
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> _v) {
  n=_n,m=_m,k=min(_k,K),h=_h,v=_v;
  for(int i=0;i<n;++i){
    for(int j=0;j<=k;++j) di[i][j]=INF;
    g[i]=vector<pair<int,int>>();
    vi[i]=false;
  }
  for(int i=0;i<m;++i)
    g[x[i]].emplace_back(c[i],y[i]),
    g[y[i]].emplace_back(c[i],x[i]);
  pq.emplace(0.0,make_pair(0,0)); di[0][0]=0.0;
  find0(0);
  for(int i=0;i<n;++i) if(v[i]==0&&vi[i])
    pq.emplace(0.0,make_pair(i,0)),di[i][0]=0.0;
  while(pq.size()){
    auto [d,p]=pq.top(); pq.pop();
    int i=p.first,j=p.second; d=-d;
    if(i==h) continue;
    if(d>di[i][j]) continue;

    if(v[i]==0){
      for(auto&[w,x]:g[i])
        if(di[x][j]>(double)w) pq.emplace(-(di[x][j]=(double)w),make_pair(x,j));
    }else if(v[i]==1){
      for(auto&[w,x]:g[i])
        if(di[x][j]>d+(double)w) pq.emplace(-(di[x][j]=d+(double)w),make_pair(x,j));
    }else{  // v[i]==2
      for(auto&[w,x]:g[i]){
        if(d+(double)w<di[x][j]) pq.emplace(-(di[x][j]=d+(double)w),make_pair(x,j));
        double nd=d/2.0;
        if(j<k&&nd+(double)w<di[x][j+1]) pq.emplace(-(di[x][j+1]=nd+(double)w),make_pair(x,j+1));
      }
    }
  }
  double ans=INF;
  for(int j=0;j<=k;++j) ans=min(ans,di[h][j]);
  return ans==INF?-1.0:ans;
}

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