oj.uz

Submission #778737

# Submission time Handle Problem Language Result Execution time Memory
778737 2023-07-10T15:57:17 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 178188 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100010;
vector<pair<int, int>> g[MAX];
double dist[MAX * 100];
double lst[MAX * 100];

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> a) {
  k = min(k, 70);
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < m; i++) {
    g[x[i]].emplace_back(y[i], c[i]);
    g[y[i]].emplace_back(x[i], c[i]);
  }
  const double inf = 1e18;
  k += 1;
  for (int i = 0; i < n * k; i++) {
    dist[i] = inf;
    lst[i] = inf;
  }
  dist[0] = 0;
  priority_queue<pair<double, int>> pq;
  pq.push({0, 0});
  double ans = inf;
  while (!pq.empty()) {
    auto it = pq.top();
    int v = it.second;
    pq.pop();
    int i = v / k;
    int j = v % k;
    if (i == h) {
      ans = min(ans, dist[v]);
      continue;
    }
    if (lst[v] <= dist[v]) {
      continue;
    }
    if (a[i] == 0) {
      for (int x = 0; x < k; x++) {
        if (dist[i * k + x] != 0) {
          dist[i * k + x] = 0;
          pq.push({dist[i * k + x], i * k + x});
        }
      }
    }
    lst[v] = dist[v];
    for (auto& p : g[i]) {
      int to = p.first;
      int w = p.second;
      if (a[to] == 0) {
        if (dist[to * k + j] > 0) {
          int nto = to * k + j;
          /* if (st.find({dist[nto], nto}) != st.end()) {
            st.erase(st.find({dist[nto], nto}));
          } */
          dist[nto] = 0;
          pq.push({-dist[nto], nto});
        }
      }
      if (dist[to * k + j] > dist[v] + w) {
        int nto = to * k + j;
        /* if (st.find({dist[nto], nto}) != st.end()) {
          st.erase(st.find({dist[nto], nto}));
        } */
        dist[nto] = dist[v] + w;
        pq.push({-dist[nto], nto});
      }
      if (a[to] == 2) {
        if (j + 1 < k && dist[to * k + j + 1] > (dist[v] + w) / 2.000000) {
          int nto = to * k + j + 1;
          /* if (st.find({dist[nto], nto}) != st.end()) {
            st.erase(st.find({dist[nto], nto}));
          } */
          dist[nto] = (dist[v] + w) / 2.000000;
          pq.push({-dist[nto], nto});
        }
      }
    }
  }
  if (ans == inf) {
    ans = -1;
  }
  return ans;
}

/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4

4.00000000000

1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4

2.00000000000
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Correct.
2 Correct 22 ms 2800 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3248 KB Correct.
2 Correct 22 ms 3284 KB Correct.
3 Correct 20 ms 3248 KB Correct.
4 Correct 21 ms 3292 KB Correct.
5 Correct 21 ms 3288 KB Correct.
6 Correct 20 ms 8148 KB Correct.
7 Correct 26 ms 7964 KB Correct.
8 Correct 15 ms 13488 KB Correct.
9 Correct 23 ms 2780 KB Correct.
10 Correct 19 ms 2784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 3352 KB Correct.
2 Correct 240 ms 3516 KB Correct.
3 Correct 228 ms 3568 KB Correct.
4 Correct 213 ms 2788 KB Correct.
5 Correct 215 ms 2804 KB Correct.
6 Correct 47 ms 7760 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 34688 KB Correct.
2 Correct 420 ms 3308 KB Correct.
3 Correct 364 ms 3516 KB Correct.
4 Correct 391 ms 3352 KB Correct.
5 Correct 358 ms 2928 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3284 KB Correct.
2 Correct 20 ms 3284 KB Correct.
3 Correct 19 ms 3332 KB Correct.
4 Correct 21 ms 8164 KB Correct.
5 Correct 17 ms 2776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3560 KB Correct.
2 Correct 113 ms 3648 KB Correct.
3 Correct 47 ms 44456 KB Correct.
4 Correct 84 ms 8800 KB Correct.
5 Correct 125 ms 2772 KB Correct.
6 Correct 129 ms 3652 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 4268 KB Correct.
2 Correct 51 ms 5164 KB Correct.
3 Correct 821 ms 38140 KB Correct.
4 Correct 815 ms 12144 KB Correct.
5 Correct 1049 ms 57368 KB Correct.
6 Correct 398 ms 28072 KB Correct.
7 Correct 859 ms 11800 KB Correct.
8 Correct 916 ms 4504 KB Correct.
9 Correct 334 ms 4272 KB Correct.
10 Correct 348 ms 4804 KB Correct.
11 Correct 952 ms 3656 KB Correct.
12 Correct 369 ms 4224 KB Correct.
13 Correct 371 ms 4312 KB Correct.
14 Correct 626 ms 13620 KB Correct.
15 Correct 872 ms 6812 KB Correct.
16 Correct 351 ms 4276 KB Correct.
17 Correct 431 ms 4140 KB Correct.
18 Correct 425 ms 4196 KB Correct.
19 Correct 1143 ms 4204 KB Correct.
20 Correct 29 ms 2968 KB Correct.
21 Correct 29 ms 3644 KB Correct.
22 Correct 37 ms 5696 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1591 ms 7776 KB Correct.
2 Correct 193 ms 10840 KB Correct.
3 Correct 629 ms 120216 KB Correct.
4 Correct 2073 ms 9304 KB Correct.
5 Execution timed out 3084 ms 178188 KB Time limit exceeded
6 Halted 0 ms 0 KB -