oj.uz

Submission #778733

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

using namespace std;

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

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);
  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) {
          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 17 ms 2772 KB Correct.
2 Correct 18 ms 2756 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3316 KB Correct.
2 Correct 22 ms 3296 KB Correct.
3 Correct 21 ms 3252 KB Correct.
4 Correct 21 ms 3284 KB Correct.
5 Correct 21 ms 3284 KB Correct.
6 Correct 21 ms 8148 KB Correct.
7 Correct 26 ms 7972 KB Correct.
8 Correct 16 ms 13604 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 23 ms 3260 KB Correct.
2 Correct 23 ms 3264 KB Correct.
3 Correct 23 ms 3324 KB Correct.
4 Correct 22 ms 2772 KB Correct.
5 Correct 27 ms 2768 KB Correct.
6 Correct 7 ms 7124 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 34600 KB Correct.
2 Correct 522 ms 3304 KB Correct.
3 Correct 453 ms 3340 KB Correct.
4 Correct 478 ms 3240 KB Correct.
5 Correct 404 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3316 KB Correct.
2 Correct 20 ms 3248 KB Correct.
3 Correct 20 ms 3344 KB Correct.
4 Correct 23 ms 8176 KB Correct.
5 Correct 19 ms 2784 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3288 KB Correct.
2 Correct 18 ms 3248 KB Correct.
3 Correct 47 ms 44544 KB Correct.
4 Correct 15 ms 6712 KB Correct.
5 Correct 20 ms 2772 KB Correct.
6 Correct 19 ms 3320 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 4880 KB Correct.
2 Correct 51 ms 5176 KB Correct.
3 Correct 1505 ms 37032 KB Correct.
4 Correct 1227 ms 11936 KB Correct.
5 Correct 1123 ms 57392 KB Correct.
6 Correct 382 ms 28072 KB Correct.
7 Correct 1187 ms 11820 KB Correct.
8 Correct 1191 ms 4504 KB Correct.
9 Correct 373 ms 4296 KB Correct.
10 Correct 388 ms 4872 KB Correct.
11 Correct 1163 ms 3660 KB Correct.
12 Correct 400 ms 4268 KB Correct.
13 Correct 393 ms 4848 KB Correct.
14 Correct 963 ms 13772 KB Correct.
15 Correct 1319 ms 6904 KB Correct.
16 Correct 362 ms 4232 KB Correct.
17 Correct 481 ms 4252 KB Correct.
18 Correct 465 ms 4268 KB Correct.
19 Correct 1411 ms 4748 KB Correct.
20 Correct 27 ms 2772 KB Correct.
21 Correct 32 ms 3796 KB Correct.
22 Correct 33 ms 5716 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 10888 KB Correct.
2 Correct 229 ms 11336 KB Correct.
3 Correct 740 ms 135768 KB Correct.
4 Execution timed out 3080 ms 10496 KB Time limit exceeded
5 Halted 0 ms 0 KB -