oj.uz

Submission #778783

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

using namespace std;

const double eps = 1e-7;

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

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, 66);
  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) {
        was[j] = true;
      }
      if (!was[j]) {
        was[j] = true;
        que.push_back(j);
      }
    }
  }
  if (!was[h]) {
    return -1;
  }
  const double inf = 1e15;
  k += 1;
  que.push_back(h);
  for (int i : que) {
    for (int j = 0; j < k; j++) {
      dist[i * k + j] = inf;
      lst[i * k + j] = inf;
    }
  }
  priority_queue<pair<double, int>> pq;
  for (int j : que) {
    if (j == 0 || a[j] == 0) {
      dist[j * k] = 0;
      pq.push({dist[j * k], 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]);
      if (ans <= eps) {
        return ans;
      }
      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 (to == 0 || a[to] == 0) {
        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 16 ms 2772 KB Correct.
2 Correct 15 ms 2812 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3272 KB Correct.
2 Correct 23 ms 3300 KB Correct.
3 Correct 21 ms 3300 KB Correct.
4 Correct 24 ms 3284 KB Correct.
5 Correct 22 ms 3296 KB Correct.
6 Correct 22 ms 8148 KB Correct.
7 Correct 28 ms 8124 KB Correct.
8 Correct 17 ms 13720 KB Correct.
9 Correct 22 ms 2772 KB Correct.
10 Correct 20 ms 2748 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3272 KB Correct.
2 Correct 27 ms 3276 KB Correct.
3 Correct 22 ms 3232 KB Correct.
4 Correct 24 ms 2772 KB Correct.
5 Correct 22 ms 2776 KB Correct.
6 Correct 7 ms 7252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 15376 KB Correct.
2 Correct 193 ms 3408 KB Correct.
3 Correct 169 ms 3520 KB Correct.
4 Correct 172 ms 3308 KB Correct.
5 Correct 159 ms 2816 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3368 KB Correct.
2 Correct 20 ms 3284 KB Correct.
3 Correct 20 ms 3284 KB Correct.
4 Correct 22 ms 8164 KB Correct.
5 Correct 26 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3296 KB Correct.
2 Correct 17 ms 3316 KB Correct.
3 Correct 32 ms 7832 KB Correct.
4 Correct 14 ms 6224 KB Correct.
5 Correct 26 ms 2764 KB Correct.
6 Correct 19 ms 3300 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 3752 KB Correct.
2 Correct 30 ms 4232 KB Correct.
3 Correct 603 ms 38404 KB Correct.
4 Correct 447 ms 12500 KB Correct.
5 Correct 685 ms 57524 KB Correct.
6 Correct 321 ms 28232 KB Correct.
7 Correct 458 ms 12152 KB Correct.
8 Correct 437 ms 4568 KB Correct.
9 Correct 156 ms 4000 KB Correct.
10 Correct 155 ms 4124 KB Correct.
11 Correct 425 ms 3616 KB Correct.
12 Correct 163 ms 4128 KB Correct.
13 Correct 176 ms 4068 KB Correct.
14 Correct 364 ms 13100 KB Correct.
15 Correct 447 ms 6852 KB Correct.
16 Correct 147 ms 3932 KB Correct.
17 Correct 185 ms 3888 KB Correct.
18 Correct 168 ms 3780 KB Correct.
19 Correct 372 ms 3736 KB Correct.
20 Correct 13 ms 2900 KB Correct.
21 Correct 12 ms 3324 KB Correct.
22 Correct 26 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 5724 KB Correct.
2 Correct 78 ms 6796 KB Correct.
3 Correct 617 ms 114292 KB Correct.
4 Correct 963 ms 9200 KB Correct.
5 Correct 2267 ms 110452 KB Correct.
6 Correct 1219 ms 83440 KB Correct.
7 Correct 1037 ms 38360 KB Correct.
8 Correct 1106 ms 5496 KB Correct.
9 Correct 494 ms 6908 KB Correct.
10 Correct 470 ms 7228 KB Correct.
11 Correct 1652 ms 3076 KB Correct.
12 Correct 525 ms 7312 KB Correct.
13 Correct 596 ms 7052 KB Correct.
14 Execution timed out 3065 ms 112464 KB Time limit exceeded
15 Halted 0 ms 0 KB -