oj.uz

Submission #778730

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

using namespace std;

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, 80);
  vector<vector<pair<int, int>>> g(n);
  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;
  vector<double> dist(n * k, inf);
  dist[0] = 0;
  set<pair<double, int>> st;
  st.emplace(0, 0);
  double ans = inf;
  vector<double> lst(n * k, inf);
  while (!st.empty()) {
    auto it = st.begin();
    int v = it->second;
    st.erase(it);
    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) {
          int nto = to * k + j;
          /* if (st.find({dist[nto], nto}) != st.end()) {
            st.erase(st.find({dist[nto], nto}));
          } */
          dist[nto] = 0;
          st.emplace(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;
        st.emplace(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;
          st.emplace(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 24 ms 468 KB Correct.
2 Correct 25 ms 464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1312 KB Correct.
2 Correct 29 ms 1180 KB Correct.
3 Correct 28 ms 1300 KB Correct.
4 Correct 29 ms 1124 KB Correct.
5 Correct 29 ms 1172 KB Correct.
6 Correct 28 ms 6860 KB Correct.
7 Correct 35 ms 7048 KB Correct.
8 Correct 19 ms 11672 KB Correct.
9 Correct 32 ms 436 KB Correct.
10 Correct 31 ms 440 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1140 KB Correct.
2 Correct 30 ms 1032 KB Correct.
3 Correct 27 ms 1088 KB Correct.
4 Correct 28 ms 432 KB Correct.
5 Correct 28 ms 420 KB Correct.
6 Correct 7 ms 4904 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 33612 KB Correct.
2 Correct 519 ms 1160 KB Correct.
3 Correct 416 ms 1148 KB Correct.
4 Correct 459 ms 1236 KB Correct.
5 Correct 313 ms 480 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1176 KB Correct.
2 Correct 28 ms 1136 KB Correct.
3 Correct 27 ms 1056 KB Correct.
4 Correct 26 ms 5792 KB Correct.
5 Correct 26 ms 496 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1076 KB Correct.
2 Correct 27 ms 1340 KB Correct.
3 Correct 60 ms 43900 KB Correct.
4 Correct 18 ms 5020 KB Correct.
5 Correct 25 ms 340 KB Correct.
6 Correct 27 ms 1116 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 1628 KB Correct.
2 Correct 29 ms 2120 KB Correct.
3 Correct 1796 ms 38476 KB Correct.
4 Correct 1321 ms 12584 KB Correct.
5 Correct 1123 ms 80932 KB Correct.
6 Correct 563 ms 41104 KB Correct.
7 Correct 1248 ms 10072 KB Correct.
8 Correct 1104 ms 2180 KB Correct.
9 Correct 241 ms 1720 KB Correct.
10 Correct 247 ms 1684 KB Correct.
11 Correct 1080 ms 1144 KB Correct.
12 Correct 267 ms 1900 KB Correct.
13 Correct 231 ms 1796 KB Correct.
14 Correct 1144 ms 12816 KB Correct.
15 Correct 1429 ms 4124 KB Correct.
16 Correct 216 ms 1664 KB Correct.
17 Correct 282 ms 1892 KB Correct.
18 Correct 313 ms 1584 KB Correct.
19 Correct 854 ms 2544 KB Correct.
20 Correct 18 ms 468 KB Correct.
21 Correct 21 ms 1292 KB Correct.
22 Correct 26 ms 4304 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 4496 KB Correct.
2 Correct 93 ms 5716 KB Correct.
3 Correct 901 ms 135880 KB Correct.
4 Execution timed out 3086 ms 9340 KB Time limit exceeded
5 Halted 0 ms 0 KB -