oj.uz

Submission #778792

# Submission time Handle Problem Language Result Execution time Memory
778792 2023-07-10T16:52:35 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
100 / 100
 1286 ms 114252 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-7;

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

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, 66);
  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]);
  }
  vector<int> que(1, 0);
  vector<bool> was(n, false);
  was[0] = true;
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& p : g[i]) {
      int j = p.first;
      if (j == h) {
        was[j] = true;
      }
      if (!was[j]) {
        was[j] = true;
        que.push_back(j);
      }
    }
  }
  if (!was[h]) {
    return -1;
  }
  const double inf = 1e15;
  k += 1;
  que.push_back(h);
  for (int i : que) {
    for (int j = 0; j < k; j++) {
      dist[i * k + j] = inf;
      lst[i * k + j] = inf;
    }
  }
  priority_queue<pair<int, pair<double, int>>> pq;
  for (int j : que) {
    if (j == 0 || a[j] == 0) {
      dist[j * k] = 0;
      pq.push({0, {dist[j * k], j * k}});
    }
  }
  double ans = inf;
  while (!pq.empty()) {
    auto it = pq.top();
    int v = it.second.second;
    pq.pop();
    int i = v / k;
    int j = v % k;
    if (i == h) {
      ans = min(ans, dist[v]);
      if (ans <= eps) {
        return ans;
      }
      continue;
    }
    if (lst[v] <= dist[v] + eps) {
      continue;
    }
    lst[v] = dist[v];
    for (auto& p : g[i]) {
      int to = p.first;
      int w = p.second;
      if (to == 0 || a[to] == 0) {
        continue;
      }
      if (dist[to * k + j] > dist[v] + w + eps) {
        int nto = to * k + j;
        dist[nto] = dist[v] + w;
        pq.push({-j, {-dist[nto], nto}});
      }
      if (a[to] == 2) {
        if (j + 1 < k && dist[to * k + j + 1] > (dist[v] + w) / 2.000000 + eps) {
          int nto = to * k + j + 1;
          dist[nto] = (dist[v] + w) / 2.000000;
          pq.push({-(j + 1), {-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 15 ms 2836 KB Correct.
2 Correct 15 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3292 KB Correct.
2 Correct 23 ms 3336 KB Correct.
3 Correct 22 ms 3308 KB Correct.
4 Correct 23 ms 3300 KB Correct.
5 Correct 24 ms 3292 KB Correct.
6 Correct 22 ms 8192 KB Correct.
7 Correct 29 ms 8148 KB Correct.
8 Correct 17 ms 13652 KB Correct.
9 Correct 23 ms 2772 KB Correct.
10 Correct 21 ms 2776 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3284 KB Correct.
2 Correct 25 ms 3324 KB Correct.
3 Correct 22 ms 3284 KB Correct.
4 Correct 23 ms 2768 KB Correct.
5 Correct 23 ms 2768 KB Correct.
6 Correct 8 ms 7252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13752 KB Correct.
2 Correct 77 ms 3148 KB Correct.
3 Correct 69 ms 3176 KB Correct.
4 Correct 72 ms 3120 KB Correct.
5 Correct 45 ms 2780 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3344 KB Correct.
2 Correct 23 ms 3236 KB Correct.
3 Correct 19 ms 3288 KB Correct.
4 Correct 24 ms 8324 KB Correct.
5 Correct 19 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3268 KB Correct.
2 Correct 17 ms 3284 KB Correct.
3 Correct 31 ms 7732 KB Correct.
4 Correct 16 ms 6300 KB Correct.
5 Correct 20 ms 2772 KB Correct.
6 Correct 19 ms 3336 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3316 KB Correct.
2 Correct 15 ms 3284 KB Correct.
3 Correct 650 ms 36528 KB Correct.
4 Correct 264 ms 11800 KB Correct.
5 Correct 341 ms 26244 KB Correct.
6 Correct 152 ms 12544 KB Correct.
7 Correct 269 ms 11560 KB Correct.
8 Correct 201 ms 4256 KB Correct.
9 Correct 68 ms 3308 KB Correct.
10 Correct 63 ms 3296 KB Correct.
11 Correct 178 ms 3416 KB Correct.
12 Correct 75 ms 3304 KB Correct.
13 Correct 78 ms 3388 KB Correct.
14 Correct 260 ms 11364 KB Correct.
15 Correct 241 ms 6328 KB Correct.
16 Correct 72 ms 3292 KB Correct.
17 Correct 84 ms 3284 KB Correct.
18 Correct 76 ms 3256 KB Correct.
19 Correct 179 ms 3308 KB Correct.
20 Correct 6 ms 2644 KB Correct.
21 Correct 6 ms 2900 KB Correct.
22 Correct 14 ms 3668 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3740 KB Correct.
2 Correct 27 ms 3840 KB Correct.
3 Correct 895 ms 114252 KB Correct.
4 Correct 298 ms 7300 KB Correct.
5 Correct 686 ms 46344 KB Correct.
6 Correct 308 ms 18280 KB Correct.
7 Correct 529 ms 24920 KB Correct.
8 Correct 256 ms 4376 KB Correct.
9 Correct 130 ms 4044 KB Correct.
10 Correct 115 ms 3824 KB Correct.
11 Correct 122 ms 2944 KB Correct.
12 Correct 138 ms 3820 KB Correct.
13 Correct 147 ms 3916 KB Correct.
14 Correct 1286 ms 46980 KB Correct.
15 Correct 1185 ms 59024 KB Correct.
16 Correct 484 ms 23384 KB Correct.
17 Correct 295 ms 7548 KB Correct.
18 Correct 133 ms 4420 KB Correct.
19 Correct 157 ms 4140 KB Correct.
20 Correct 141 ms 4188 KB Correct.
21 Correct 344 ms 3796 KB Correct.
22 Correct 8 ms 2800 KB Correct.
23 Correct 11 ms 3184 KB Correct.
24 Correct 25 ms 4212 KB Correct.