Submission #1174273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174273		sqrteipi	Cyberland (APIO23_cyberland)	C++20	0 / 100	841 ms	25216 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, l, r) for (int i = l; i < r; i++)
template <class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> ARR) {
  K = min(K, 50);
  const double INF = 1e18;
  vector<pair<int, int>> G[N + 1];
  bool vis[N][K + 1];
  double dist[N][K + 1];
  REP(i, 0, N) REP(j, 0, K + 1) vis[i][j] = false, dist[i][j] = INF;
  REP(i, 0, M) G[X[i]].push_back({Y[i], C[i]}), G[Y[i]].push_back({X[i], C[i]});
  REP(i, 0, K + 1) {
    min_heap<pair<double, int>> pq;
    REP(j, 0, N) {
      if (j == 0 || ARR[j] == 0) dist[j][i] = 0;
      for (auto [v, w] : G[j]) pq.push({dist[j][i] + w, v});
      dist[j][i] = INF;
      if (j == 0 || ARR[j] == 0) dist[j][i] = 0;
    }
    while (!pq.empty()) {
      auto [d, u] = pq.top(); pq.pop();
      if (vis[u][i]) continue;
      vis[u][i] = true; dist[u][i] = d;
      if (i < K) dist[u][i + 1] = min(dist[u][i + 1], d / 2);
      for (auto [v, w] : G[u]) {
        if (dist[u][i] + w < dist[v][i]) {
          dist[v][i] = dist[u][i] + w;
          pq.push({dist[v][i], v});
        }
      }
    }
  }
  return *min_element(dist[H], dist[H] + K + 1);
}

// int main() {
//   // cout << fixed << setprecision(10) << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});
//   cout << fixed << setprecision(10) << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});
// }

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