Submission #760432

#	Time	Username	Problem	Language	Result	Execution time	Memory
760432		wiwiho	Cyberland (APIO23_cyberland)	C++17	97 / 100	1006 ms	84092 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

double solve(int n, int m, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr){

    K = min(K, 40);   
    vector<ld> frac(K + 1); // 2^-i
    frac[0] = 1;
    for(int i = 1; i <= K; i++) frac[i] = frac[i - 1] / 2;

    vector<vector<pii>> g(n);
    for(int i = 0; i < m; i++){
        g[U[i]].pb(mp(V[i], W[i]));
        g[V[i]].pb(mp(U[i], W[i]));
    }

    vector<bool> ok(n);
    {
        queue<int> q;
        q.push(0);
        ok[0] = true;
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(auto [v, w] : g[now]){
                if(v == H) continue;
                if(ok[v]) continue;
                ok[v] = true;
                q.push(v);
            }
        }
    }

    vector<vector<ld>> dis(n, vector<ld>(K + 1, 1e100));
    priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<>> pq;
    vector<vector<bool>> vst(n, vector<bool>(K + 1));

    dis[H][0] = 0;
    pq.push(mp(0, mp(H, 0)));
    
    auto relax = [&](int now, int k, ld d){
        if(k > K) return;
        for(auto [v, w] : g[now]){
            if(v == H) continue;
            if(d + w * frac[k] >= dis[v][k]) continue;
            dis[v][k] = d + w * frac[k];
            pq.push(mp(dis[v][k], mp(v, k)));
        }
    };

    ld ans = 1e100;
    
    while(!pq.empty()){
        ld d = pq.top().ff;
        auto [now, k] = pq.top().ss;
        pq.pop();
        if(vst[now][k]) continue;
        if((ok[now] && arr[now] == 0) || now == 0) ans = min(ans, d);
        vst[now][k] = true;
        relax(now, k, d);
        if(arr[now] == 2) relax(now, k + 1, d);
    }

    if(ans > 1e20) return -1;
    else return ans;
}

• 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: 0 / 3