oj.uz

Submission #778716

# Submission time Handle Problem Language Result Execution time Memory
778716 2023-07-10T15:35:17 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
0 / 100
 3000 ms 1669376 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

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) {
  vector<vector<pair<int, int>>> g(n);
  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]);
  }
  const double inf = 1e18;
  k += 1;
  vector<double> dist(n * k, inf);
  dist[0] = 0;
  set<pair<double, int>> st;
  st.emplace(0, 0);
  double ans = inf;
  while (!st.empty()) {
    auto it = st.begin();
    int v = it->second;
    st.erase(it);
    int i = v / k;
    int j = v % k;
    if (i == n - 1) {
      ans = min(ans, dist[v]);
      continue;
    }
    for (auto& p : g[i]) {
      int to = p.first;
      int w = p.second;
      if (dist[to * k + j] > dist[v] + w) {
        int nto = to * k + j;
        if (st.find({dist[nto], nto}) != st.end()) {
          st.erase(st.find({dist[nto], nto}));
        }
        dist[nto] = dist[v] + w;
        st.emplace(dist[nto], nto);
      }
      if (a[to] == 0) {
        if (dist[to * k + j] > 0) {
          int nto = to * k + j;
          if (st.find({dist[nto], nto}) != st.end()) {
            st.erase(st.find({dist[nto], nto}));
          }
          dist[nto] = 0;
          st.emplace(dist[nto], nto);
        }
      }
      if (a[to] == 2) {
        if (j + 1 < k && dist[to * k + j + 1] > (dist[v] + w) / 2) {
          int nto = to * k + j + 1;
          if (st.find({dist[nto], nto}) != st.end()) {
            st.erase(st.find({dist[nto], nto}));
          }
          dist[nto] = (dist[v] + w) / 2;
          st.emplace(dist[nto], nto);
        }
      }
    }
  }
  return (ans == inf ? -1 : 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
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 460 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1196 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 1616 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1340 ms 20460 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1588 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1624 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 1988 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3135 ms 1669376 KB Time limit exceeded
2 Halted 0 ms 0 KB -