oj.uz

Submission #778778

# Submission time Handle Problem Language Result Execution time Memory
778778 2023-07-10T16:39:17 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 114232 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) {
      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]);
      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 2732 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3280 KB Correct.
2 Correct 22 ms 3288 KB Correct.
3 Correct 21 ms 3316 KB Correct.
4 Correct 22 ms 3288 KB Correct.
5 Correct 22 ms 3284 KB Correct.
6 Correct 22 ms 8204 KB Correct.
7 Correct 28 ms 8020 KB Correct.
8 Correct 17 ms 13716 KB Correct.
9 Correct 21 ms 2772 KB Correct.
10 Correct 20 ms 2768 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3276 KB Correct.
2 Correct 25 ms 3468 KB Correct.
3 Correct 22 ms 3284 KB Correct.
4 Correct 23 ms 2768 KB Correct.
5 Correct 22 ms 2784 KB Correct.
6 Correct 7 ms 7252 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 15292 KB Correct.
2 Correct 191 ms 3424 KB Correct.
3 Correct 163 ms 3348 KB Correct.
4 Correct 169 ms 3324 KB Correct.
5 Correct 148 ms 2808 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3284 KB Correct.
2 Correct 20 ms 3232 KB Correct.
3 Correct 20 ms 3296 KB Correct.
4 Correct 24 ms 8148 KB Correct.
5 Correct 17 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3332 KB Correct.
2 Correct 18 ms 3352 KB Correct.
3 Correct 31 ms 7864 KB Correct.
4 Correct 15 ms 6180 KB Correct.
5 Correct 20 ms 2764 KB Correct.
6 Correct 19 ms 3348 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 3812 KB Correct.
2 Correct 26 ms 4228 KB Correct.
3 Correct 609 ms 38424 KB Correct.
4 Correct 462 ms 12596 KB Correct.
5 Correct 665 ms 57624 KB Correct.
6 Correct 319 ms 28124 KB Correct.
7 Correct 438 ms 12248 KB Correct.
8 Correct 441 ms 4472 KB Correct.
9 Correct 169 ms 4200 KB Correct.
10 Correct 171 ms 4168 KB Correct.
11 Correct 427 ms 3628 KB Correct.
12 Correct 174 ms 4140 KB Correct.
13 Correct 188 ms 4100 KB Correct.
14 Correct 369 ms 13104 KB Correct.
15 Correct 445 ms 6800 KB Correct.
16 Correct 166 ms 4056 KB Correct.
17 Correct 199 ms 3864 KB Correct.
18 Correct 202 ms 3932 KB Correct.
19 Correct 455 ms 3752 KB Correct.
20 Correct 14 ms 2880 KB Correct.
21 Correct 15 ms 3352 KB Correct.
22 Correct 27 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 5880 KB Correct.
2 Correct 77 ms 6772 KB Correct.
3 Correct 613 ms 114232 KB Correct.
4 Correct 987 ms 9168 KB Correct.
5 Correct 2341 ms 110532 KB Correct.
6 Correct 1157 ms 83176 KB Correct.
7 Correct 1035 ms 38204 KB Correct.
8 Correct 1109 ms 5324 KB Correct.
9 Correct 575 ms 7728 KB Correct.
10 Correct 570 ms 7256 KB Correct.
11 Correct 1643 ms 2976 KB Correct.
12 Correct 565 ms 7172 KB Correct.
13 Correct 635 ms 7120 KB Correct.
14 Execution timed out 3074 ms 112244 KB Time limit exceeded
15 Halted 0 ms 0 KB -