Submission #981996

#	Time	Username	Problem	Language	Result	Execution time	Memory
981996		vjudge1	Cyberland (APIO23_cyberland)	C++17	97 / 100	682 ms	37964 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using id = pair <ll, double>;
using vii = vector <id>;

const ll MAXN = 1E5+16;
const double INF = double(1E18)+16;
vii adj[MAXN];
double dis[31*MAXN];

double solve (int n, int m, int k, int h, vi u, vi v, vi vw, vi arr) {
    fill(adj, adj+n, vii({}));
    for (ll i = 0; i < 31*n; i++) dis[i] = INF;
    for (ll i = 0; i < m; i++) {
        adj[u[i]].push_back({ v[i], double(vw[i]) });
        adj[v[i]].push_back({ u[i], double(vw[i]) });
    }
    vector <char> vis(n, false);
    queue <ll> q;
    q.push(0);
    vis[0] = true;
    while (q.size()) {
        ll u = q.front(); q.pop();
        if (u == h) continue;
        for (auto [v, w] : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            q.push(v);
        }
    }
    if (!vis[h]) return -1;
    priority_queue <pair <ll, pair <double, ll> > > pq;
    dis[0] = 0;
    pq.push({ 0, { 0, 0 } });
    for (ll u = 1; u < n; u++) {
        if (vis[u] && arr[u] == 0) {
            dis[u] = 0;
            pq.push({ 0, { 0, u } });
        }
    }
    vis.assign(31*n, false);
    while (pq.size()) {
        ll ou = pq.top().second.second; pq.pop();
        if (vis[ou]) continue;
        vis[ou] = true;
        ll u = ou%n;
        if (u == h) continue; // once you reach cyberland you cannot move
        ll lvl = ou/n;
        for (auto [v, w] : adj[u]) {
            ll ov = v+lvl*n;
            if (arr[v] == 2 && lvl < 30) {
                if (dis[ov+n] > (dis[ou]+w)/2) {
                    dis[ov+n] = (dis[ou]+w)/2;
                    pq.push({ -(lvl+1), { -dis[ov+n], ov+n } });
                }
            }
            if (dis[ov] <= dis[ou]+w) continue;
            dis[ov] = dis[ou]+w;
            pq.push({ -lvl, { -dis[ov], ov } });
        }
    }
    double ans = INF;
    for (ll i = 0; i <= k; i++) {
        ans = min(ans, dis[h+i*n]);
    }
    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