Submission #957910

#	Time	Username	Problem	Language	Result	Execution time	Memory
957910		MtSaka	Cyberland (APIO23_cyberland)	C++17	15 / 100	931 ms	39788 KiB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
using ld=long double;
static constexpr ld eps=1e-8;
struct UnionFind{
    private:
    vector<int>par;
    public:
    UnionFind(int n):par(n,-1){}
    int root(int v){return par[v]<0?v:par[v]=root(par[v]);}
    bool same(int u,int v){return root(u)==root(v);}
    bool merge(int u,int v){
        u=root(u),v=root(v);
        if(u==v)return false;
        if(par[u]>par[v])swap(u,v);
        par[u]+=par[v];
        par[v]=u;
        return true;
    }
};
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){
    chmin(K,100);
    vector<vector<ld>>dist(N,vector<ld>(K+1,inf));
    vector<vector<pair<ll,ll>>>g(N);
    UnionFind uf(N);
    rep(i,M){
        g[x[i]].eb(y[i],c[i]);
        g[y[i]].eb(x[i],c[i]);
        uf.merge(x[i],y[i]);
    }
    priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>pq;
    rep(i,N){
        if(uf.same(0,i)&&(i==0||arr[i]==0)){
            dist[i][K]=0;
            pq.emplace(0,i,K);
        }
    }
    for(int i=0;i<=K;++i){
        priority_queue<tuple<ld,ll,ll>,vector<tuple<ld,ll,ll>>,greater<>>npq;
        while(!pq.empty()){
            auto [d,v,k]=pq.top();pq.pop();
            if(d-dist[v][k]>eps)continue;
            if(v==H)continue;
            for(auto [u,cost]:g[v]){
                if(dist[u][k]-(ld)(d+cost)>eps){
                    dist[u][k]=(ld)(d+cost);
                    pq.emplace(dist[u][k],u,k);
                }
                if(k-1>=0&&arr[u]==2&&dist[u][k-1]-(ld(d+cost)/2.0)>eps){
                    dist[u][k-1]=(ld)(d+cost)/2.0;
                    npq.emplace(dist[u][k-1],u,k-1);
                }
            }
        }
        pq=move(npq);
    }
    ld res=inf;
    rep(i,K+1)chmin(res,dist[H][i]);
    if(res==inf)return -1;
    return res;
}

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