Submission #806430

#	Time	Username	Problem	Language	Result	Execution time	Memory
806430		irmuun	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	176 ms	67032 KiB

cyberland

#include<bits/stdc++.h>
#include "cyberland.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const double inf=1e18;
 
struct dsu{
    vector<ll>p,sz;
    void init(ll n){
        p.resize(n);
        iota(p.begin(),p.end(),0);
        sz.resize(n);
        fill(sz.begin(),sz.end(),1);
    }
    ll find(ll x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x==y){
            return true;
        }
        else{
            return false;
        }
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            p[y]=x;
        }
    }
}ds;
 
double solve(int N, int M, int K, int H, vector<int>x, vector<int>y, vector<int>c, vector<int>arr){
    K=min(K,70);
    vector<double>pw(K+1);
    ds.init(N);
    vector<pair<int,int>>adj[N];
    for(int i=0;i<M;i++){
        if(x[i]!=H&&y[i]!=H){
            ds.merge(x[i],y[i]);
        }
        adj[x[i]].pb({c[i],y[i]});
        adj[y[i]].pb({c[i],x[i]});
    }
    pw[0]=1;
    for(int i=1;i<=K;i++){
        pw[i]=pw[i-1]/2;
    }
    arr[0]=0;
    vector<vector<double>>dist(K+1,vector<double>(N,inf));
    using node=tuple<double,int,int>;
    priority_queue<node,vector<node>,greater<node>>pq;
    auto ck=[&](int k,int x,double d){
        if(dist[k][x]>d){
            dist[k][x]=d;
            pq.push({d,k,x});
        }
    };
    ck(K,H,0);
    while(!pq.empty()){
        auto [d,k,x]=pq.top();
        pq.pop();
        if(dist[k][x]<d){
            continue;
        }
        if(arr[x]==0){
            return d;
        }
        for(auto [c,y]:adj[x]){
            if(!ds.same(y,0)){
                continue;
            }
            ck(k,y,d+c*pw[K-k]);
            if(arr[x]==2&&k>0){
                ck(k-1,y,d+c*pw[K-k+1]);
            }
        }
    }
    return -1;
}

• 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