oj.uz

Submission #778735

# Submission time Handle Problem Language Result Execution time Memory
778735 2023-07-10T15:56:19 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 185592 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;
    }
    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 2748 KB Correct.
2 Correct 22 ms 2824 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3300 KB Correct.
2 Correct 21 ms 3288 KB Correct.
3 Correct 20 ms 3284 KB Correct.
4 Correct 21 ms 3268 KB Correct.
5 Correct 21 ms 3284 KB Correct.
6 Correct 21 ms 8148 KB Correct.
7 Correct 25 ms 8060 KB Correct.
8 Correct 15 ms 13596 KB Correct.
9 Correct 19 ms 2780 KB Correct.
10 Correct 23 ms 2768 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3384 KB Correct.
2 Correct 240 ms 3392 KB Correct.
3 Correct 224 ms 3436 KB Correct.
4 Correct 217 ms 2912 KB Correct.
5 Correct 215 ms 2784 KB Correct.
6 Correct 46 ms 7688 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 34688 KB Correct.
2 Correct 422 ms 3344 KB Correct.
3 Correct 364 ms 3380 KB Correct.
4 Correct 395 ms 3304 KB Correct.
5 Correct 352 ms 2864 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3456 KB Correct.
2 Correct 20 ms 3284 KB Correct.
3 Correct 20 ms 3272 KB Correct.
4 Correct 21 ms 8156 KB Correct.
5 Correct 17 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3544 KB Correct.
2 Correct 113 ms 3612 KB Correct.
3 Correct 65 ms 44624 KB Correct.
4 Correct 84 ms 8864 KB Correct.
5 Correct 125 ms 2816 KB Correct.
6 Correct 131 ms 3676 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 4232 KB Correct.
2 Correct 51 ms 5200 KB Correct.
3 Correct 818 ms 38008 KB Correct.
4 Correct 821 ms 12088 KB Correct.
5 Correct 1072 ms 57456 KB Correct.
6 Correct 369 ms 28072 KB Correct.
7 Correct 858 ms 11828 KB Correct.
8 Correct 912 ms 4488 KB Correct.
9 Correct 356 ms 4264 KB Correct.
10 Correct 343 ms 4804 KB Correct.
11 Correct 940 ms 3660 KB Correct.
12 Correct 357 ms 4160 KB Correct.
13 Correct 366 ms 4296 KB Correct.
14 Correct 616 ms 13696 KB Correct.
15 Correct 890 ms 6940 KB Correct.
16 Correct 336 ms 4224 KB Correct.
17 Correct 428 ms 4192 KB Correct.
18 Correct 405 ms 4240 KB Correct.
19 Correct 1116 ms 4400 KB Correct.
20 Correct 28 ms 2944 KB Correct.
21 Correct 29 ms 3616 KB Correct.
22 Correct 33 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1857 ms 10156 KB Correct.
2 Correct 231 ms 11488 KB Correct.
3 Correct 726 ms 135820 KB Correct.
4 Correct 2303 ms 10380 KB Correct.
5 Execution timed out 3034 ms 185592 KB Time limit exceeded
6 Halted 0 ms 0 KB -