oj.uz

Submission #778786

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

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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
*/

Compilation message

cyberland.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
cyberland.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2772 KB Correct.
2 Correct 15 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3276 KB Correct.
2 Correct 22 ms 3292 KB Correct.
3 Correct 22 ms 3284 KB Correct.
4 Correct 26 ms 3280 KB Correct.
5 Correct 31 ms 3224 KB Correct.
6 Correct 26 ms 8220 KB Correct.
7 Correct 27 ms 8020 KB Correct.
8 Correct 19 ms 13676 KB Correct.
9 Correct 20 ms 2772 KB Correct.
10 Correct 20 ms 2772 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3212 KB Correct.
2 Correct 24 ms 3280 KB Correct.
3 Correct 23 ms 3232 KB Correct.
4 Correct 22 ms 2772 KB Correct.
5 Correct 22 ms 2780 KB Correct.
6 Correct 7 ms 7188 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 15332 KB Correct.
2 Correct 192 ms 3508 KB Correct.
3 Correct 161 ms 3408 KB Correct.
4 Correct 168 ms 3316 KB Correct.
5 Correct 148 ms 2824 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3356 KB Correct.
2 Correct 20 ms 3212 KB Correct.
3 Correct 19 ms 3332 KB Correct.
4 Correct 22 ms 8232 KB Correct.
5 Correct 17 ms 2780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3292 KB Correct.
2 Correct 17 ms 3284 KB Correct.
3 Correct 31 ms 7736 KB Correct.
4 Correct 16 ms 6212 KB Correct.
5 Correct 19 ms 2772 KB Correct.
6 Correct 22 ms 3344 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 3756 KB Correct.
2 Correct 26 ms 4164 KB Correct.
3 Correct 615 ms 38464 KB Correct.
4 Correct 494 ms 12528 KB Correct.
5 Correct 676 ms 57536 KB Correct.
6 Correct 319 ms 28148 KB Correct.
7 Correct 440 ms 12156 KB Correct.
8 Correct 439 ms 4576 KB Correct.
9 Correct 148 ms 4084 KB Correct.
10 Correct 141 ms 4088 KB Correct.
11 Correct 426 ms 3660 KB Correct.
12 Correct 159 ms 4176 KB Correct.
13 Correct 191 ms 4112 KB Correct.
14 Correct 382 ms 13072 KB Correct.
15 Correct 432 ms 6864 KB Correct.
16 Correct 145 ms 3916 KB Correct.
17 Correct 183 ms 3832 KB Correct.
18 Correct 167 ms 3868 KB Correct.
19 Correct 376 ms 3688 KB Correct.
20 Correct 13 ms 2900 KB Correct.
21 Correct 12 ms 3352 KB Correct.
22 Correct 26 ms 5704 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 5724 KB Correct.
2 Correct 80 ms 6816 KB Correct.
3 Correct 583 ms 114244 KB Correct.
4 Correct 965 ms 9012 KB Correct.
5 Correct 2278 ms 110380 KB Correct.
6 Correct 1195 ms 83264 KB Correct.
7 Correct 1053 ms 38312 KB Correct.
8 Correct 1104 ms 5284 KB Correct.
9 Correct 510 ms 6824 KB Correct.
10 Correct 481 ms 7348 KB Correct.
11 Correct 1743 ms 2984 KB Correct.
12 Correct 524 ms 7268 KB Correct.
13 Correct 602 ms 7192 KB Correct.
14 Execution timed out 3093 ms 112328 KB Time limit exceeded
15 Halted 0 ms 0 KB -