Submission #1194902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194902		ackhava	Cyberland (APIO23_cyberland)	C++20	40 / 100	274 ms	43456 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#pragma GCC optimize "O3,unroll-loops,trapv"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2"
#define fi first
#define se second
#define pb push_back
#define REP(i,o,n) for(auto i=o;i<n;i++)
using namespace std;
// #define __int128 long long

double cost[200100][70];
double mem[70];
vector<pair<int, double>> adj[200100];
vector<int> arr;
vector<int> src;

void dfs(int node, int H){
    if(cost[node][0]>0)return;
    cost[node][0]=100;
    if(arr[node]==0)src.pb(node);
    if(src.size()&&src.back()==H)return;
    if(node==H)return;
    for(auto i:adj[node])dfs(i.fi,H);
}

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) {
    REP(i,0,N+10)adj[i].clear();
    REP(i,0,N+10)REP(j,0,70)cost[i][j]=-2e9;
    ::arr=arr;
    src.clear();
    REP(i,0,M){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i],c[i]});
    }
    double tmp=1;
    REP(i,0,70)mem[i]=tmp,tmp*=2;
    src.pb(0);
    dfs(0,H);
    REP(i,0,N+10)REP(j,0,70)cost[i][j]=-2e9;
    if(src.size() && src.back()==H)return 0;
    K = min(K,67);
    // return src.size();
    priority_queue<pair<double,pair<int,int>>,vector<pair<double,pair<int,int>>>,greater<pair<double,pair<int,int>>>> pq;
    for(auto i:src)pq.push({0,{i,0}});
    while(pq.size()){
        auto top=pq.top();pq.pop();
        assert(top.fi>=0);
        if(top.se.se > K)continue;
        if(cost[top.se.fi][top.se.se]>=-1)continue;
        cost[top.se.fi][top.se.se]=top.fi;
        // cerr<<"POS "<<top.se.fi<<", JUMP "<<top.se.se<<": "<<(long long)top.fi<<endl;
        if(top.se.fi == H)continue;
        for(auto i:adj[top.se.fi]){
            if(arr[i.fi]==2)pq.push({top.fi+mem[top.se.se]*i.se,{i.fi,top.se.se+1}});
            pq.push({top.fi+mem[top.se.se]*i.se,{i.fi,top.se.se}});
        }
    }
    // return cost[H][0];
    long double ans=cost[H][0];
    assert(ans>=-1);
    // assert(0);
    long double div=1;
    REP(i,0,K+1){
        if(cost[H][i]>=-1)ans=(min(ans,((long double)cost[H][i])/div));
        div*=2;
    }
    return ans;
}

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