oj.uz

Submission #778746

# Submission time Handle Problem Language Result Execution time Memory
778746 2023-07-10T16:04:30 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 1402 ms 112204 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, 65);
  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});
            }
          }
        }
      }
      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 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3280 KB Correct.
2 Correct 22 ms 3284 KB Correct.
3 Correct 21 ms 3240 KB Correct.
4 Correct 21 ms 3284 KB Correct.
5 Correct 23 ms 3284 KB Correct.
6 Correct 27 ms 8100 KB Correct.
7 Correct 27 ms 8020 KB Correct.
8 Correct 16 ms 13524 KB Correct.
9 Correct 20 ms 2784 KB Correct.
10 Correct 20 ms 2780 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3376 KB Correct.
2 Correct 229 ms 3384 KB Correct.
3 Correct 212 ms 3424 KB Correct.
4 Correct 215 ms 2788 KB Correct.
5 Correct 204 ms 2788 KB Correct.
6 Correct 46 ms 7772 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 34700 KB Correct.
2 Correct 445 ms 3348 KB Correct.
3 Correct 379 ms 3380 KB Correct.
4 Correct 411 ms 3312 KB Correct.
5 Correct 358 ms 2864 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3284 KB Correct.
2 Correct 25 ms 3212 KB Correct.
3 Correct 24 ms 3324 KB Correct.
4 Correct 25 ms 8184 KB Correct.
5 Correct 18 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3536 KB Correct.
2 Correct 113 ms 3692 KB Correct.
3 Correct 48 ms 44484 KB Correct.
4 Correct 80 ms 8760 KB Correct.
5 Correct 139 ms 2820 KB Correct.
6 Correct 128 ms 3696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 4244 KB Correct.
2 Correct 52 ms 5184 KB Correct.
3 Correct 838 ms 38052 KB Correct.
4 Correct 868 ms 12160 KB Correct.
5 Correct 1088 ms 57436 KB Correct.
6 Correct 399 ms 28072 KB Correct.
7 Correct 888 ms 11836 KB Correct.
8 Correct 954 ms 4568 KB Correct.
9 Correct 355 ms 4316 KB Correct.
10 Correct 348 ms 4940 KB Correct.
11 Correct 982 ms 3660 KB Correct.
12 Correct 355 ms 4188 KB Correct.
13 Correct 393 ms 4320 KB Correct.
14 Correct 623 ms 13636 KB Correct.
15 Correct 885 ms 6844 KB Correct.
16 Correct 348 ms 4248 KB Correct.
17 Correct 440 ms 4344 KB Correct.
18 Correct 412 ms 4260 KB Correct.
19 Correct 1134 ms 4316 KB Correct.
20 Correct 32 ms 2944 KB Correct.
21 Correct 29 ms 3612 KB Correct.
22 Correct 35 ms 5748 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1402 ms 7724 KB Correct.
2 Correct 190 ms 8608 KB Correct.
3 Incorrect 620 ms 112204 KB Wrong Answer.
4 Halted 0 ms 0 KB -