Submission #755370

#	Time	Username	Problem	Language	Result	Execution time	Memory
755370		IloveN	Cyberland (APIO23_cyberland)	C++17	97 / 100	3046 ms	163200 KiB

cyberland

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(), vr.end()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;

struct vertex {
    int v, d;
    double dist;

    bool operator < (const vertex &obj) const {
        return mp(dist, v) > mp(obj.dist, obj.v);
    }
};

const int N = 1e5 + 10;
vector<pii> G[N];
int vis[N];
double dist[N][82];

void dfs(int u, vi& vt, int del) {
    vis[u] = 1;
    vt.eb(u);
    for (pii pa : G[u])
        if (!vis[pa.fi] && pa.fi != del) dfs(pa.fi, vt, del);
}

double solve(int n, int m, int k, int h, vi x, vi y, vi c, vi arr) {
    k = min(k, 80);
    for (int i = 0; i < n; ++i) G[i].clear();
    for (int i = 0; i < m; ++i) {
        int u = x[i], v = y[i], w = c[i];
        G[u].eb(v, w);
        G[v].eb(u, w);
    }
    for (int i = 0; i < n; ++i) vis[i] = 0;
    vi vt;
    dfs(0, vt, h);
    priority_queue<vertex> q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= k; ++j) dist[i][j] = 1e18;
    dist[0][0] = 0;
    q.push({0, 0, 0});
    for (int x : vt)
        if (!arr[x]) dist[x][0] = 0, q.push({x, 0, 0});
    while (!q.empty()) {
        int u = q.top().v, d = q.top().d;
        double w = q.top().dist;
        q.pop();
        if (w != dist[u][d] || u == h) continue;
        for (pii pa : G[u]) {
            if (dist[u][d] + pa.se < dist[pa.fi][d]) {
                dist[pa.fi][d] = dist[u][d] + pa.se;
                q.push({pa.fi, d, dist[pa.fi][d]});
            }
            if (arr[u] == 2 && d < k && dist[u][d] / 2 + pa.se < dist[pa.fi][d + 1]) {
                dist[pa.fi][d + 1] = dist[u][d] / 2 + pa.se;
                q.push({pa.fi, d + 1, dist[pa.fi][d + 1]});
            }
        }
    }
    double res = 1e18;
    for (int i = 0; i <= k; ++i) res = min(res, dist[h][i]);
    if (res == 1e18) res = -1;
    return res;
}

• 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