oj.uz

Submission #958982

# Submission time Handle Problem Language Result Execution time Memory
958982 2024-04-07T10:44:00 Z nguyentunglam Cyberland (APIO23_cyberland) C++17
97 / 100
 400 ms 58960 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

int a[N];

double d[31][N];

bool vis[31][N];

bool _vis[N];

vector<int> start;

vector<pair<int, int> > adj[N];

int n, h, k;

#define ii pair<double, int>

priority_queue<ii, vector<ii>, greater<ii> > q[31];

void dfs(int u) {
  _vis[u] = 1;
  if (a[u] == 0 || u == 0) q[0].push({d[0][u] = 0, u});
  for(auto &[v, w] : adj[u]) if (!_vis[v] && v != h) dfs(v);
}

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> arr) {
  n = N;
  h = H;
  k = K;
  for(int i = 0; i < n; i++) adj[i].clear(), _vis[i] = 0;
  for(int i = 0; i < x.size(); i++) {
    adj[x[i]].emplace_back(y[i], c[i]);
    adj[y[i]].emplace_back(x[i], c[i]);
  }
  for(int j = 0; j <= k; j++) for(int i = 0; i < n; i++) d[j][i] = 1e17, vis[j][i] = 0;
  for(int i = 0; i < n; i++) a[i] = arr[i];
  dfs(0);
  for(int j = 0; j <= k; j++) {
    while (!q[j].empty()) {
      auto [cost, u] = q[j].top(); q[j].pop();
      if (vis[j][u]) continue;
      vis[j][u] = 1;
      if (u == h) continue;
      for(auto &[v, w] : adj[u]) {
        if (j < k && a[u] == 2 && d[j + 1][v] > d[j][u] / 2 + w) q[j + 1].push({d[j + 1][v] = d[j][u] / 2 + w, v});
        if (d[j][v] > d[j][u] + w) q[j].push({d[j][v] = d[j][u] + w, v});
      }
    }
  }

  double ans = 1e18;
  for(int j = 0; j <= k; j++) ans = min(ans, d[j][h]);

  if (ans > 1e16) ans = -1;

  return ans;
}

#ifdef ngu
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}
#endif // ngu

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0; i < x.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29532 KB Correct.
2 Correct 20 ms 29788 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29532 KB Correct.
2 Correct 25 ms 29272 KB Correct.
3 Correct 27 ms 29500 KB Correct.
4 Correct 24 ms 29276 KB Correct.
5 Correct 30 ms 29508 KB Correct.
6 Correct 22 ms 30040 KB Correct.
7 Correct 34 ms 30044 KB Correct.
8 Correct 15 ms 30888 KB Correct.
9 Correct 22 ms 29336 KB Correct.
10 Correct 23 ms 29272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 29276 KB Correct.
2 Correct 29 ms 29532 KB Correct.
3 Correct 27 ms 29560 KB Correct.
4 Correct 24 ms 29276 KB Correct.
5 Correct 24 ms 29428 KB Correct.
6 Correct 9 ms 30044 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 38536 KB Correct.
2 Correct 92 ms 29784 KB Correct.
3 Correct 81 ms 29780 KB Correct.
4 Correct 85 ms 29728 KB Correct.
5 Correct 49 ms 29264 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29528 KB Correct.
2 Correct 23 ms 30556 KB Correct.
3 Correct 27 ms 30560 KB Correct.
4 Correct 25 ms 31476 KB Correct.
5 Correct 20 ms 30044 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29532 KB Correct.
2 Correct 20 ms 30296 KB Correct.
3 Correct 37 ms 37160 KB Correct.
4 Correct 16 ms 30812 KB Correct.
5 Correct 22 ms 30280 KB Correct.
6 Correct 22 ms 30552 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 29788 KB Correct.
2 Correct 20 ms 30044 KB Correct.
3 Correct 323 ms 32352 KB Correct.
4 Correct 223 ms 29648 KB Correct.
5 Correct 400 ms 55884 KB Correct.
6 Correct 183 ms 46104 KB Correct.
7 Correct 219 ms 33896 KB Correct.
8 Correct 169 ms 31752 KB Correct.
9 Correct 89 ms 30772 KB Correct.
10 Correct 91 ms 30540 KB Correct.
11 Correct 150 ms 31572 KB Correct.
12 Correct 107 ms 30800 KB Correct.
13 Correct 109 ms 30712 KB Correct.
14 Correct 206 ms 34020 KB Correct.
15 Correct 192 ms 32596 KB Correct.
16 Correct 95 ms 30952 KB Correct.
17 Correct 110 ms 31052 KB Correct.
18 Correct 107 ms 30660 KB Correct.
19 Correct 287 ms 31736 KB Correct.
20 Correct 9 ms 29272 KB Correct.
21 Correct 11 ms 29528 KB Correct.
22 Correct 18 ms 30804 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 58960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -