oj.uz

Submission #778712

# Submission time Handle Problem Language Result Execution time Memory
778712 2023-07-10T15:29:41 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
0 / 100
 3000 ms 1826852 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], to}) != 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], to}) != 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], to}) != 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 18 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
0.0 / 7.0

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

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 397 ms 2540 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 3133 ms 1826852 KB Time limit exceeded
2 Halted 0 ms 0 KB -