oj.uz

Submission #778750

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

using namespace std;

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

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, 68);
  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;
    }
    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) {
          for (int x = 0; x < k; x++) {
            if (dist[to * k + x] != 0) {
              dist[to * k + x] = 0;
              pq.push({dist[to * k + x], to * k + x});
            }
          }
        }
        continue;
      }
      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 23 ms 2772 KB Correct.
2 Correct 22 ms 2816 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3248 KB Correct.
2 Correct 22 ms 3284 KB Correct.
3 Correct 22 ms 3296 KB Correct.
4 Correct 21 ms 3268 KB Correct.
5 Correct 21 ms 3284 KB Correct.
6 Correct 27 ms 8176 KB Correct.
7 Correct 26 ms 8020 KB Correct.
8 Correct 16 ms 13524 KB Correct.
9 Correct 19 ms 2764 KB Correct.
10 Correct 19 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 3376 KB Correct.
2 Correct 254 ms 3468 KB Correct.
3 Correct 215 ms 3404 KB Correct.
4 Correct 203 ms 2788 KB Correct.
5 Correct 227 ms 2892 KB Correct.
6 Correct 45 ms 7760 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 34644 KB Correct.
2 Correct 443 ms 3344 KB Correct.
3 Correct 383 ms 3336 KB Correct.
4 Correct 391 ms 3436 KB Correct.
5 Correct 349 ms 2804 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3352 KB Correct.
2 Correct 25 ms 3284 KB Correct.
3 Correct 24 ms 3284 KB Correct.
4 Correct 22 ms 8160 KB Correct.
5 Correct 17 ms 2776 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 3552 KB Correct.
2 Correct 108 ms 3612 KB Correct.
3 Correct 48 ms 44480 KB Correct.
4 Correct 81 ms 8800 KB Correct.
5 Correct 137 ms 2820 KB Correct.
6 Correct 124 ms 3672 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 4196 KB Correct.
2 Correct 52 ms 5164 KB Correct.
3 Correct 846 ms 38016 KB Correct.
4 Correct 907 ms 12156 KB Correct.
5 Correct 1062 ms 57464 KB Correct.
6 Correct 429 ms 28080 KB Correct.
7 Correct 874 ms 11820 KB Correct.
8 Correct 934 ms 4552 KB Correct.
9 Correct 350 ms 4352 KB Correct.
10 Correct 358 ms 4892 KB Correct.
11 Correct 971 ms 3656 KB Correct.
12 Correct 365 ms 4296 KB Correct.
13 Correct 385 ms 4260 KB Correct.
14 Correct 643 ms 13688 KB Correct.
15 Correct 878 ms 6820 KB Correct.
16 Correct 330 ms 4292 KB Correct.
17 Correct 427 ms 4160 KB Correct.
18 Correct 422 ms 4216 KB Correct.
19 Correct 1119 ms 4396 KB Correct.
20 Correct 31 ms 2944 KB Correct.
21 Correct 33 ms 3592 KB Correct.
22 Correct 38 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1526 ms 7732 KB Correct.
2 Correct 183 ms 8704 KB Correct.
3 Correct 698 ms 116884 KB Correct.
4 Correct 2053 ms 9236 KB Correct.
5 Execution timed out 3058 ms 177064 KB Time limit exceeded
6 Halted 0 ms 0 KB -