Submission #959192

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959192	2024-04-07T15:55:39 Z	kilkuwu	Cyberland (APIO23_cyberland)	C++17	100 / 100	1303 ms	10816 KB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>

template <typename T>
using PQG = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

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) {
  std::vector<std::vector<std::pair<int, int>>> adj(N);
  for (int i = 0; i < M; i++) {
    int u = x[i], v = y[i], w = c[i];
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  PQG<std::pair<double, int>> pq;
  double ans = 1e18;

  std::vector<double> dp(N, 1e18);
  pq.emplace(0, 0);
  dp[0] = 0;

  K = std::min(K, 100);

  for (int kk = 0; kk <= K; kk++) {
    std::vector<double> ndp(N, 1e18);
    PQG<std::pair<double, int>> npq;

    while (pq.size()) {
      auto [d, u] = pq.top();
      pq.pop();

      if (u == H) continue;

      if (d > dp[u]) continue;

      for (auto [v, w] : adj[u]) {
        if (arr[v] <= 1) {
          auto nd = (d + w) * arr[v];
          if (nd < dp[v]) {
            dp[v] = nd;
            pq.emplace(nd, v);
          }
        } else {
          auto nd = d + w;
          if (nd < dp[v]) {
            dp[v] = nd;
            pq.emplace(nd, v);
          }
          nd /= 2;
          if (nd < ndp[v]) {
            ndp[v] = nd;
            npq.emplace(nd, v);
          }
        }
      }
    }

    ans = std::min(ans, dp[H]);
    std::swap(pq, npq);
    std::swap(dp, ndp);
  }

  return (ans < 1e18 ? ans : -1);
}

#ifdef LOCAL
#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}
#endif

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	600 KB	Correct.
2	Correct	20 ms	540 KB	Correct.

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	600 KB	Correct.
2	Correct	26 ms	816 KB	Correct.
3	Correct	22 ms	604 KB	Correct.
4	Correct	23 ms	604 KB	Correct.
5	Correct	25 ms	600 KB	Correct.
6	Correct	21 ms	1440 KB	Correct.
7	Correct	31 ms	1440 KB	Correct.
8	Correct	10 ms	2648 KB	Correct.
9	Correct	21 ms	348 KB	Correct.
10	Correct	24 ms	784 KB	Correct.

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	348 KB	Correct.
2	Correct	30 ms	344 KB	Correct.
3	Correct	25 ms	604 KB	Correct.
4	Correct	24 ms	348 KB	Correct.
5	Correct	23 ms	344 KB	Correct.
6	Correct	5 ms	1116 KB	Correct.

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	6704 KB	Correct.
2	Correct	100 ms	592 KB	Correct.
3	Correct	82 ms	596 KB	Correct.
4	Correct	91 ms	596 KB	Correct.
5	Correct	49 ms	344 KB	Correct.

Subtask #5
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	604 KB	Correct.
2	Correct	22 ms	348 KB	Correct.
3	Correct	21 ms	604 KB	Correct.
4	Correct	19 ms	1308 KB	Correct.
5	Correct	19 ms	348 KB	Correct.

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	604 KB	Correct.
2	Correct	20 ms	608 KB	Correct.
3	Correct	32 ms	8500 KB	Correct.
4	Correct	13 ms	1208 KB	Correct.
5	Correct	22 ms	540 KB	Correct.
6	Correct	21 ms	604 KB	Correct.

Subtask #7
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	600 KB	Correct.
2	Correct	17 ms	604 KB	Correct.
3	Correct	345 ms	10816 KB	Correct.
4	Correct	241 ms	4868 KB	Correct.
5	Correct	371 ms	9900 KB	Correct.
6	Correct	188 ms	7072 KB	Correct.
7	Correct	244 ms	4048 KB	Correct.
8	Correct	205 ms	2792 KB	Correct.
9	Correct	89 ms	1496 KB	Correct.
10	Correct	90 ms	1452 KB	Correct.
11	Correct	175 ms	2388 KB	Correct.
12	Correct	114 ms	1464 KB	Correct.
13	Correct	101 ms	1620 KB	Correct.
14	Correct	226 ms	7140 KB	Correct.
15	Correct	227 ms	3904 KB	Correct.
16	Correct	97 ms	1580 KB	Correct.
17	Correct	116 ms	1620 KB	Correct.
18	Correct	121 ms	1480 KB	Correct.
19	Correct	313 ms	2332 KB	Correct.
20	Correct	5 ms	472 KB	Correct.
21	Correct	8 ms	604 KB	Correct.
22	Correct	14 ms	1116 KB	Correct.

Subtask #8
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	276 ms	788 KB	Correct.
2	Correct	47 ms	604 KB	Correct.
3	Correct	146 ms	10576 KB	Correct.
4	Correct	315 ms	1116 KB	Correct.
5	Correct	1169 ms	9576 KB	Correct.
6	Correct	503 ms	7072 KB	Correct.
7	Correct	579 ms	6764 KB	Correct.
8	Correct	252 ms	2844 KB	Correct.
9	Correct	208 ms	1432 KB	Correct.
10	Correct	206 ms	1364 KB	Correct.
11	Correct	148 ms	2016 KB	Correct.
12	Correct	251 ms	1444 KB	Correct.
13	Correct	229 ms	1540 KB	Correct.
14	Correct	1303 ms	7736 KB	Correct.
15	Correct	1031 ms	7812 KB	Correct.
16	Correct	420 ms	4444 KB	Correct.
17	Correct	293 ms	2744 KB	Correct.
18	Correct	222 ms	1628 KB	Correct.
19	Correct	287 ms	1616 KB	Correct.
20	Correct	257 ms	1556 KB	Correct.
21	Correct	867 ms	2588 KB	Correct.
22	Correct	10 ms	344 KB	Correct.
23	Correct	18 ms	604 KB	Correct.
24	Correct	38 ms	1116 KB	Correct.

Submission #959192

Compilation message