제출 #755053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755053		ttamx	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	2955 ms	142972 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

typedef double db;
typedef tuple<db,int,int,bool> t4;

const int N=1e5+5;
const int K=75;

int n,m,k,h;
int a[N];
db dp[N][K][2];
bool vis[N][K][2];
vector<pair<int,db>> adj[N];
priority_queue<t4,vector<t4>,greater<t4>> pq;

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    n=N,m=M,k=min(K,70),h=H;
    for(int i=0;i<n;i++)adj[i].clear();
    for(int i=0;i<m;i++){
        int u=x[i],v=y[i],w=c[i];
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    for(int i=0;i<n;i++)a[i]=arr[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i][j][1]=DBL_MAX;
            vis[i][j][0]=vis[i][j][1]=false;
        }
    }
    while(!pq.empty())pq.pop();
    pq.emplace(0,h,0,0);
    for(int i=0;i<=k;i++)dp[h][i][0]=dp[h][i][1]=0;
    while(!pq.empty()){
        auto [d,u,s,f]=pq.top();
        pq.pop();
        if(vis[u][s][f])continue;
        vis[u][s][f]=true;
        for(auto [v,w]:adj[u]){
            db res=d+(f?0:w/pow(2.0,s));
            if(res>=dp[v][s][f])continue;
            dp[v][s][f]=res;
            pq.emplace(res,v,s,f);
        }
        if(a[u]==0&&f==0){
            for(auto [v,w]:adj[u]){
                db res=d;
                if(res>=dp[v][s][1])continue;
                dp[v][s][1]=res;
                pq.emplace(res,v,s,1);
            }
        }
        if(a[u]==2&&s<k){
            for(auto [v,w]:adj[u]){
                db res=d+(f?0:w/pow(2.0,s+1));
                if(res>=dp[v][s+1][f])continue;
                dp[v][s+1][f]=res;
                pq.emplace(res,v,s+1,f);
            }
        }
    }
    db ans=DBL_MAX;
    for(int i=0;i<=k;i++)ans=min({ans,dp[0][i][0],dp[0][i][1]});
    if(ans==DBL_MAX)ans=-1;
    return 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: 3 / 3