제출 #1194881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194881		dzuizz	Cyberland (APIO23_cyberland)	C++20	97 / 100	3049 ms	160772 KiB

cyberland

#pragma GCC optimize("Ofast,unroll-loops")
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
constexpr double INF=DBL_MAX;
constexpr int N = 1e5;
constexpr int K = 71;
int n,m,k,h;
vector<pair<int,int>> g[N];
double di[N][K];
vector<int> v;
bool vi[N];
priority_queue<pair<double,int>> pq; // (-d,i,j)
void find0(int u){
if(v[u]==0)
pq.emplace(0.0,K*u),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> _v) {
n=_n,m=_m,k=min(_k,K-1),h=_h,v=_v;
for(int i=0;i<n;++i){
g[i].clear();
vi[i]=0;
for(int j=0;j<=k;++j){
di[i][j]=INF;
}
}
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,0); di[0][0]=0;
find0(0);
while(pq.size()){
auto [d,p]=pq.top(); pq.pop();
int i=p/K,j=p%K; d=-d;
if(i==h) continue;
if(d>di[i][j]) continue;
for(auto&[w,x]:g[i]){
if(v[i]==0){
if(di[x][j]>w) pq.emplace(-(di[x][j]=w),K*x+j);
}else if(v[i]==1){
if(di[x][j]>d+w) pq.emplace(-(di[x][j]=d+w),K*x+j);
}else{ // v[i]==2
if(d+w<di[x][j]) pq.emplace(-(di[x][j]=d+w),K*x+j);
double nd=d/2.0;
if(j<k&&nd+w<di[x][j+1]) pq.emplace(-(di[x][j+1]=nd+w),K*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