oj.uz

Submission #778742

# Submission time Handle Problem Language Result Execution time Memory
778742 2023-07-10T15:58:46 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 178192 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, 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 2780 KB Correct.
2 Correct 21 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3220 KB Correct.
2 Correct 21 ms 3268 KB Correct.
3 Correct 20 ms 3284 KB Correct.
4 Correct 21 ms 3296 KB Correct.
5 Correct 20 ms 3284 KB Correct.
6 Correct 20 ms 8192 KB Correct.
7 Correct 25 ms 7964 KB Correct.
8 Correct 17 ms 13496 KB Correct.
9 Correct 19 ms 2772 KB Correct.
10 Correct 20 ms 2784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 3392 KB Correct.
2 Correct 239 ms 3388 KB Correct.
3 Correct 222 ms 3408 KB Correct.
4 Correct 217 ms 2896 KB Correct.
5 Correct 216 ms 2796 KB Correct.
6 Correct 46 ms 7760 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 34812 KB Correct.
2 Correct 422 ms 3348 KB Correct.
3 Correct 369 ms 3376 KB Correct.
4 Correct 390 ms 3344 KB Correct.
5 Correct 352 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3272 KB Correct.
2 Correct 23 ms 3336 KB Correct.
3 Correct 19 ms 3272 KB Correct.
4 Correct 21 ms 8160 KB Correct.
5 Correct 17 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3520 KB Correct.
2 Correct 113 ms 3692 KB Correct.
3 Correct 54 ms 44620 KB Correct.
4 Correct 84 ms 8756 KB Correct.
5 Correct 125 ms 2812 KB Correct.
6 Correct 132 ms 3720 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 4188 KB Correct.
2 Correct 51 ms 5164 KB Correct.
3 Correct 812 ms 38068 KB Correct.
4 Correct 814 ms 12112 KB Correct.
5 Correct 1035 ms 57364 KB Correct.
6 Correct 372 ms 28016 KB Correct.
7 Correct 843 ms 11772 KB Correct.
8 Correct 912 ms 4464 KB Correct.
9 Correct 335 ms 4292 KB Correct.
10 Correct 341 ms 4896 KB Correct.
11 Correct 930 ms 3676 KB Correct.
12 Correct 355 ms 4188 KB Correct.
13 Correct 353 ms 4304 KB Correct.
14 Correct 599 ms 13788 KB Correct.
15 Correct 844 ms 6860 KB Correct.
16 Correct 331 ms 4248 KB Correct.
17 Correct 418 ms 4152 KB Correct.
18 Correct 411 ms 4188 KB Correct.
19 Correct 1108 ms 4348 KB Correct.
20 Correct 28 ms 2944 KB Correct.
21 Correct 28 ms 3600 KB Correct.
22 Correct 35 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1548 ms 7836 KB Correct.
2 Correct 191 ms 10828 KB Correct.
3 Correct 615 ms 120116 KB Correct.
4 Correct 2068 ms 9564 KB Correct.
5 Execution timed out 3059 ms 178192 KB Time limit exceeded
6 Halted 0 ms 0 KB -