oj.uz

Submission #778776

# Submission time Handle Problem Language Result Execution time Memory
778776 2023-07-10T16:37:23 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 114288 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) {
        continue;
      }
      if (!was[j]) {
        was[j] = true;
        que.push_back(j);
      }
    }
  }
  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) {
      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) {
        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 16 ms 2832 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3280 KB Correct.
2 Correct 26 ms 3364 KB Correct.
3 Correct 22 ms 3308 KB Correct.
4 Correct 23 ms 3284 KB Correct.
5 Correct 23 ms 3256 KB Correct.
6 Correct 23 ms 8140 KB Correct.
7 Correct 29 ms 8020 KB Correct.
8 Correct 17 ms 13700 KB Correct.
9 Correct 25 ms 2776 KB Correct.
10 Correct 21 ms 2768 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3284 KB Correct.
2 Correct 29 ms 3284 KB Correct.
3 Correct 23 ms 3284 KB Correct.
4 Correct 25 ms 2764 KB Correct.
5 Correct 23 ms 2788 KB Correct.
6 Correct 7 ms 7252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 15360 KB Correct.
2 Correct 189 ms 3400 KB Correct.
3 Correct 178 ms 3452 KB Correct.
4 Correct 172 ms 3296 KB Correct.
5 Correct 152 ms 2792 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3324 KB Correct.
2 Correct 21 ms 3336 KB Correct.
3 Correct 21 ms 3412 KB Correct.
4 Correct 22 ms 8204 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 3352 KB Correct.
2 Correct 18 ms 3284 KB Correct.
3 Correct 35 ms 7852 KB Correct.
4 Correct 15 ms 6212 KB Correct.
5 Correct 20 ms 2772 KB Correct.
6 Correct 20 ms 3284 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 3868 KB Correct.
2 Correct 26 ms 4252 KB Correct.
3 Correct 648 ms 38476 KB Correct.
4 Correct 465 ms 12548 KB Correct.
5 Correct 700 ms 57516 KB Correct.
6 Correct 323 ms 28180 KB Correct.
7 Correct 484 ms 12272 KB Correct.
8 Correct 446 ms 4556 KB Correct.
9 Correct 173 ms 4220 KB Correct.
10 Correct 168 ms 4176 KB Correct.
11 Correct 461 ms 3624 KB Correct.
12 Correct 173 ms 4136 KB Correct.
13 Correct 186 ms 4128 KB Correct.
14 Correct 385 ms 13120 KB Correct.
15 Correct 441 ms 6884 KB Correct.
16 Correct 176 ms 3984 KB Correct.
17 Correct 200 ms 3868 KB Correct.
18 Correct 199 ms 3932 KB Correct.
19 Correct 458 ms 3704 KB Correct.
20 Correct 14 ms 2900 KB Correct.
21 Correct 17 ms 3272 KB Correct.
22 Correct 26 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 5856 KB Correct.
2 Correct 83 ms 6852 KB Correct.
3 Correct 600 ms 114288 KB Correct.
4 Correct 986 ms 8920 KB Correct.
5 Correct 2251 ms 110508 KB Correct.
6 Correct 1250 ms 83176 KB Correct.
7 Correct 1053 ms 38216 KB Correct.
8 Correct 1139 ms 5336 KB Correct.
9 Correct 571 ms 7620 KB Correct.
10 Correct 599 ms 7272 KB Correct.
11 Correct 1746 ms 2948 KB Correct.
12 Correct 571 ms 7316 KB Correct.
13 Correct 639 ms 6984 KB Correct.
14 Execution timed out 3065 ms 112284 KB Time limit exceeded
15 Halted 0 ms 0 KB -