Submission #884164

#	Time	Username	Problem	Language	Result	Execution time	Memory
884164		sjoonmin07	Cyberland (APIO23_cyberland)	C++17	100 / 100	180 ms	70288 KiB

cyberland

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

using dii=tuple<double,int,int>;
double dist[101010][71],p[71];
int pr[101010];
vector<pair<int,double>> adj[101010];
priority_queue<dii,vector<dii>,greater<dii>> pq;

int find_(int n) {
    if(n==pr[n]) return n;
    return pr[n]=find_(pr[n]);
}
void uni(int x,int y) {
    pr[find_(x)]=find_(y);
}

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) {
    while(!pq.empty()) pq.pop();
    for(int i=0;i<N;i++) adj[i].clear();
    K=min(K,70);
    p[0]=1;
    for(int i=1;i<=K;i++) p[i]=p[i-1]*0.5;
    for(int i=0;i<N;i++) pr[i]=i;
    for(int i=0;i<M;i++) {
        if(x[i]!=H&&y[i]!=H) uni(x[i],y[i]);
        adj[x[i]].eb(make_pair(y[i],c[i])); adj[y[i]].eb(make_pair(x[i],c[i]));
    }
    for(int i=0;i<N;i++) for(int j=0;j<=K;j++) dist[i][j]=1e18;
    for(int i=0;i<=K;i++) dist[H][i]=0;
    arr[0]=0;
    pq.push(dii(0,H,0));
    while(!pq.empty()) {
        auto [d,cur,k]=pq.top(); pq.pop();
        if(d>dist[cur][k]) continue;
        if(arr[cur]==0) return d;
        for(auto [i,c]:adj[cur]) {
            if(find_(i)!=find_(0)) continue;
            if(dist[i][k]>d+c*p[k]) {
                dist[i][k]=d+c*p[k];
                pq.push(dii(dist[i][k],i,k));
            }
            if(arr[i]==2&&k+1<=K && dist[i][k+1]>d+c*p[k]) {
                dist[i][k+1]=d+c*p[k];
                pq.push(dii(dist[i][k+1],i,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