Submission #1143540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143540		Sang	Cyberland (APIO23_cyberland)	C++20	97 / 100	3099 ms	158640 KiB

cyberland

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;

double dist[71][N];
priority_queue<pair<double, ii>, vector<pair<double, ii>>, greater<pair<double, ii>>> Q;
vector<ii> G[N];

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    K = min(K, 69);
    FOR (i, 0, N-1) FOR (j, 0, K) dist[j][i] = 1e18;
    dist[0][0] = 0;
    FOR (i, 0, M-1){
        G[x[i]].pb({y[i], c[i]});
        G[y[i]].pb({x[i], c[i]});
    }
    vi vis(N, 0);
    queue<int> q; q.push(0);
    vis[0] = 1;
    Q.push({0, {0, 0}});
    while (!q.empty()){
        int u = q.front(); q.pop();
        if (u == H) continue;
        for (ii &v : G[u]){
            if (vis[v.fi]) continue;
            if (arr[v.fi] == 0) Q.push({dist[0][v.fi] = 0, {v.fi, 0}});
            vis[v.fi] = 1;
            q.push(v.fi);
        }
    }
    double ans = 1e18;
    while (!Q.empty()){
        double w = Q.top().fi;
        int u = Q.top().se.fi, k = Q.top().se.se; Q.pop();
        if (u == H) {
            ans = min(ans, w);
            continue;
        }
        if (w != dist[k][u]) continue;
        for(ii &v : G[u]){
            double c = v.se;
            if (dist[k][v.fi] > w + c){
                Q.push({dist[k][v.fi] = w + c, {v.fi, k}});
            }
            if (k < K && arr[v.fi] == 2 && dist[k+1][v.fi] > (w + c)/2.0){
                Q.push({dist[k+1][v.fi] = (w + c)/2.0, {v.fi, k + 1}});
            }
        }
    }
    FOR (i, 0, N-1) G[i].clear();
    return (ans >= 1e18 ? -1 : 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