제출 #981839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981839		vjudge1	Cyberland (APIO23_cyberland)	C++17	44 / 100	125 ms	29364 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 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], 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();
        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 <ii> pq;
    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(31*n, false);
    while (pq.size()) {
        ll ou = pq.top().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;
        if (lvl < 30 && arr[u] == 2) { // do the /2 thingy
            ll ov = ou+n; // next level
            if (dis[ov] <= dis[ou]/2) continue;
            dis[ov] = dis[ou]/2;
            pq.push({ -dis[ov], ov });
        }
        for (auto [v, w] : adj[u]) {
            ll ov = v+lvl*n;
            if (dis[ov] <= dis[ou]+w) continue;
            dis[ov] = dis[ou]+w;
            pq.push({ -dis[ov], ov });
        }
    }
    double ans = INF;
    for (ll i = 0; i <= k; i++) {
        ans = min(ans, dis[h+i*n]);
    }
    return ans;
}

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