Submission #1194886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194886		ackhava	Cyberland (APIO23_cyberland)	C++20	0 / 100	3098 ms	137780 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

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

void dfs(int node, int H){
    if(cost[node][0]!=-1)return;
    cost[node][0]=0;
    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) {
    for(auto&i:adj)i.clear();
    memset(cost,-1,sizeof cost);
    ::arr=arr;
    src.clear();
    REP(i,0,M){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i],c[i]});
    }
    src.pb(0);
    dfs(0,H);
    memset(cost,-1,sizeof cost);
    if(src.size() && src.back()==H)return 0;
    K = min(K,68);
    priority_queue<pair<__int128,pair<int,int>>,vector<pair<__int128,pair<int,int>>>,greater<pair<__int128,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;
        __int128 mul=1;
        mul<<=top.se.se;
        for(auto i:adj[top.se.fi]){
            if(arr[i.fi]==2)pq.push({top.fi+mul*i.se,{i.fi,top.se.se+1}});
            pq.push({top.fi+mul*i.se,{i.fi,top.se.se}});
        }
    }
    long double ans=cost[H][0];
    // assert(0);
    __int128 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: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3