oj.uz

Submission #778771

# Submission time Handle Problem Language Result Execution time Memory
778771 2023-07-10T16:28:32 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 117468 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-8;

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, 68);
  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]);
  }
  vector<int> que(1, 0);
  vector<bool> was(n, false);
  was[0] = true;
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (auto& p : g[i]) {
      int j = p.first;
      if (j == h) {
        continue;
      }
      if (!was[j]) {
        was[j] = true;
        que.push_back(j);
      }
    }
  }
  const double inf = 1e15;
  k += 1;
  for (int i = 0; i < n * k; i++) {
    dist[i] = inf;
    lst[i] = inf;
  }
  priority_queue<pair<double, int>> pq;
  for (int j : que) {
    if (j == 0 || a[j] == 0) {
      for (int x = 0; x < k; x++) {
        dist[j * k + x] = 0;
      }
      pq.push({dist[j * k + 0], j * k});
    }
  }
  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] + eps) {
      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++) {
            dist[to * k + x] = 0;
            pq.push({dist[to * k + x], to * k + x});
          }
        }
        continue;
      }
      if (dist[to * k + j] > dist[v] + w + eps) {
        int nto = to * k + j;
        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 + eps) {
          int nto = to * k + j + 1;
          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 18 ms 2796 KB Correct.
2 Correct 16 ms 2792 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3332 KB Correct.
2 Correct 23 ms 3248 KB Correct.
3 Correct 21 ms 3284 KB Correct.
4 Correct 22 ms 3276 KB Correct.
5 Correct 22 ms 3284 KB Correct.
6 Correct 21 ms 8160 KB Correct.
7 Correct 27 ms 8020 KB Correct.
8 Correct 17 ms 13716 KB Correct.
9 Correct 21 ms 2780 KB Correct.
10 Correct 21 ms 2788 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3412 KB Correct.
2 Correct 24 ms 3284 KB Correct.
3 Correct 23 ms 3324 KB Correct.
4 Correct 23 ms 2772 KB Correct.
5 Correct 23 ms 2772 KB Correct.
6 Correct 7 ms 7252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 36800 KB Correct.
2 Correct 191 ms 3440 KB Correct.
3 Correct 163 ms 3492 KB Correct.
4 Correct 174 ms 3436 KB Correct.
5 Correct 152 ms 2804 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3284 KB Correct.
2 Correct 23 ms 3312 KB Correct.
3 Correct 21 ms 3284 KB Correct.
4 Correct 22 ms 8136 KB Correct.
5 Correct 18 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3344 KB Correct.
2 Correct 18 ms 3284 KB Correct.
3 Correct 47 ms 44468 KB Correct.
4 Correct 15 ms 6740 KB Correct.
5 Correct 20 ms 2768 KB Correct.
6 Correct 20 ms 3308 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 3848 KB Correct.
2 Correct 27 ms 4636 KB Correct.
3 Correct 589 ms 38432 KB Correct.
4 Correct 457 ms 12584 KB Correct.
5 Correct 661 ms 57560 KB Correct.
6 Correct 323 ms 28208 KB Correct.
7 Correct 444 ms 12156 KB Correct.
8 Correct 441 ms 4560 KB Correct.
9 Correct 177 ms 4236 KB Correct.
10 Correct 170 ms 4132 KB Correct.
11 Correct 436 ms 3624 KB Correct.
12 Correct 175 ms 4176 KB Correct.
13 Correct 188 ms 4104 KB Correct.
14 Correct 373 ms 13092 KB Correct.
15 Correct 437 ms 6844 KB Correct.
16 Correct 167 ms 4060 KB Correct.
17 Correct 204 ms 3888 KB Correct.
18 Correct 210 ms 4048 KB Correct.
19 Correct 480 ms 3752 KB Correct.
20 Correct 15 ms 2868 KB Correct.
21 Correct 15 ms 3572 KB Correct.
22 Correct 26 ms 5716 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 5884 KB Correct.
2 Correct 81 ms 7768 KB Correct.
3 Correct 606 ms 117468 KB Correct.
4 Correct 995 ms 9064 KB Correct.
5 Correct 2369 ms 111604 KB Correct.
6 Correct 1251 ms 84488 KB Correct.
7 Correct 1092 ms 40204 KB Correct.
8 Correct 1161 ms 6780 KB Correct.
9 Correct 614 ms 8328 KB Correct.
10 Correct 609 ms 8124 KB Correct.
11 Correct 1879 ms 3908 KB Correct.
12 Correct 601 ms 8156 KB Correct.
13 Correct 673 ms 7916 KB Correct.
14 Execution timed out 3061 ms 114480 KB Time limit exceeded
15 Halted 0 ms 0 KB -