제출 #1194849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194849		dzuizz	사이버랜드 (APIO23_cyberland)	C++20	44 / 100	201 ms	47432 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define ld long double
using namespace std;
constexpr int N=1e5+5,K=50;
constexpr ld INF=1e24;
int n,m,k,h;
vector<int> arr,min_nx;
vector<vector<pair<int,int>>> g;
vector<vector<ld>> di;
vector<bool> vi;
priority_queue<pair<ld,pair<int,int>>> pq;  // (-d,i,j)
void find0(int u){
  if(arr[u]==0)
    pq.emplace(0.0,make_pair(u,0)),di[u][0]=0;
  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> _arr) {
  n=_n,m=_m,k=min(_k,49),h=_h,arr=_arr;
  di=vector<vector<ld>>(n,vector<ld>(k+1,INF));
  g=vector<vector<pair<int,int>>>(n);
  min_nx=vector<int>(n,INT_MAX);
  vi=vector<bool>(n,0);
  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]);
  for(int i=0;i<n;++i) if(arr[i]==2) for(auto&[w,j]:g[i])
    if(j!=h) min_nx[i]=min(min_nx[i],w);
  pq.emplace(0.0,make_pair(0,0)); di[0][0]=0.0;
  find0(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;
    for(auto&[w,x]:g[i]){
      if(arr[x]==0){
        if(di[x][j]>0) pq.emplace(-(di[x][j]=0.0),make_pair(i,j));
      }else if(arr[x]==1){
        ld nd=d+(ld)w;
        if(nd<di[x][j]) pq.emplace(-(di[x][j]=nd),make_pair(x,j));
      }else{  // arr[x]==2
        //if(d+(ld)w<di[x][j]) pq.emplace(-(di[x][j]=d+(ld)w),make_pair(x,j));
        if(d/2.0+(ld)w<di[x][j+1]) pq.emplace(-(di[x][j+1]=d/2.0+(ld)w),make_pair(x,j+1));
        /*
        ld nd=d/2.0;
        for(int l=j+1;l<=k;++l){
          if(nd+(ld)w<di[x][l]) pq.emplace(-(di[x][l]=nd+(ld)w),make_pair(x,l));
          nd=nd/2.0+min_nx[x];
        }
        */
      }
    }
  }
  ld ans=INF;
  for(int j=0;j<=k;++j)
    ans=min(ans,di[h][j]);
  return ans==INF?-1:ans;
}

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