Submission #892480

#	Time	Username	Problem	Language	Result	Execution time	Memory
892480		d4xn	Cyberland (APIO23_cyberland)	C++17	49 / 100	3064 ms	2097152 KiB

cyberland

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

#define ld long double
#define tp3 tuple<ld, int, int>

const int N = 1e5, K = 5;
const ld D = 2, INF = LLONG_MAX;

int n, h, k;
vector<int> arr;
vector<ld> mn;
vector<vector<vector<ld>>> dis;
vector<vector<pair<int, ld>>> adj;

void dijkstra(int x, int idx) {
    priority_queue<tp3> pq;
    if (idx == 1) {
      for (int i = 0; i < n; i++) {
        if (arr[i] || dis[0][0][i] == INF) continue;
        pq.push(make_tuple(-0, 0, i));
      }
    }
    else {
      pq.push(make_tuple(-0, 0, x));
    }

    while (!pq.empty()) {
      ld d = -get<0>(pq.top());
      int divs = get<1>(pq.top());
      int y = get<2>(pq.top());
      pq.pop();

      if (dis[idx][divs][y] <= d) continue;
      dis[idx][divs][y] = d;

      if (y == h) continue;

      if (arr[y] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][y] > ((d+mn[y]) / D)) {
        pq.push(make_tuple(-((d+mn[y]) / D), divs+1, y));
      }

      for (auto& [z, d2] : adj[y]) {
        if (dis[idx][divs][z] > (d+d2)) {
          pq.push(make_tuple(-(d+d2), divs, z));
        }

        if (arr[z] == 2 && divs+1 < min(k, K) && dis[idx][divs+1][z] > ((d+d2) / D)) {
          pq.push(make_tuple(-((d+d2) / D), divs+1, z));
        }
      }
    }
}

double solve(int N, int m, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR) {
    n = N;
    h = H;
    k = K;

    arr.clear();
    arr = ARR;

    adj.clear();
    adj.resize(n);
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(make_pair(y[i], c[i]));
        adj[y[i]].push_back(make_pair(x[i], c[i]));
    }

    mn.clear();
    mn.resize(n);
    for (int i = 0; i < n; i++) {
        mn[i] = INF;
        for (auto& [j, d] : adj[i]) {
          if (j == h) continue;
          
          mn[i] = min(mn[i], d);
        }
    }

    dis.clear();
    dis.resize(2, vector<vector<ld>>(K, vector<ld>(n)));
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < K; j++) {
        for (int k = 0; k < n; k++) {
          dis[i][j][k] = INF;
        }
      }
    }
    dijkstra(0, 0);
    dijkstra(0, 1);

    ld ans = INF;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < min(K, k+1); j++) {
        ans = min(ans, dis[i][j][h]);
      }
    }

    return (ans == INF ? (ld)(-1) : ans);
}

• Subtask 1: 5 / 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