Submission #981871

#	Time	Username	Problem	Language	Result	Execution time	Memory
981871		vjudge1	Cyberland (APIO23_cyberland)	C++17	15 / 100	32 ms	8916 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 ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1E5+16;
const ll INF = ll(1E18)+16;
vii adj[MAXN];
// priority queue of long long distance :smh:
// distance/=2 is like negative-weight edge , im using dijkstra :smh:

// solution: manage the thing only at the first level
// when reaching a 2-node, simulate the while(k--) dis /= 2 and then add the rest of dis to h
//

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 < m; i++) {
        adj[u[i]].push_back({ v[i], vw[i] });
        adj[v[i]].push_back({ u[i], 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();
        for (auto [v, w] : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            q.push(v);
        }
    }
    if (!vis[h]) return -1;
    vll disToH(n, INF);
    vector <char> visToH(n, false);
    disToH[h] = 0;
    {priority_queue <ii> pq;
    pq.push({ -disToH[h], h });
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (visToH[u]) continue;
        visToH[u] = true;
        for (auto [v, w] : adj[u]) {
            if (!vis[v]) continue; // illegal
            if (disToH[v] <= disToH[u]+w) continue;
            disToH[v] = disToH[u]+w;
            pq.push({ -disToH[v], v });
        }
    }}
    priority_queue <ii> pq;
    vll dis(n, INF);
    dis[0] = 0;
    pq.push({ 0, 0 });
    for (ll u = 1; u < n; u++) {
        if (vis[u] && arr[u] == 0) {
            dis[u] = 0;
            pq.push({ 0, u });
        }
    }
    vis.assign(n, false);
    double den = 1;
    for (ll i = 0; i < min(k, 60); i++) den *= 2;
    double ans = INF;
    while (pq.size()) {
        ll u = pq.top().second; pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        if (arr[u] == 2) {
            ans = min(ans, dis[u]/den + double(disToH[u]));
        } else {
            ans = min(ans, double(dis[u] + disToH[u]));
        }
        if (u == h) continue; // once you reach cyberland you cannot move
        for (auto [v, w] : adj[u]) {
            if (dis[v] <= dis[u]+w) continue;
            dis[v] = dis[u]+w;
            pq.push({ -dis[v], v });
        }
    }
    return ans;
}

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