oj.uz

Submission #778719

# Submission time Handle Problem Language Result Execution time Memory
778719 2023-07-10T15:39:38 Z MilosMilutinovic Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 2004100 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 == h) {
      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.000000) {
          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.000000  ;
          st.emplace(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 19 ms 468 KB Correct.
2 Correct 20 ms 716 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1180 KB Correct.
2 Correct 31 ms 1784 KB Correct.
3 Correct 26 ms 1776 KB Correct.
4 Correct 28 ms 1748 KB Correct.
5 Correct 27 ms 1580 KB Correct.
6 Correct 25 ms 6176 KB Correct.
7 Correct 34 ms 4672 KB Correct.
8 Correct 14 ms 7380 KB Correct.
9 Correct 25 ms 1108 KB Correct.
10 Correct 24 ms 1120 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1756 KB Correct.
2 Correct 32 ms 1728 KB Correct.
3 Correct 29 ms 1808 KB Correct.
4 Correct 30 ms 668 KB Correct.
5 Correct 32 ms 1096 KB Correct.
6 Correct 7 ms 3160 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 20464 KB Correct.
2 Correct 601 ms 1612 KB Correct.
3 Correct 489 ms 1676 KB Correct.
4 Correct 525 ms 1736 KB Correct.
5 Correct 360 ms 1128 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1524 KB Correct.
2 Correct 25 ms 1672 KB Correct.
3 Correct 25 ms 1688 KB Correct.
4 Correct 27 ms 3888 KB Correct.
5 Correct 21 ms 1104 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1612 KB Correct.
2 Correct 23 ms 1508 KB Correct.
3 Correct 48 ms 26900 KB Correct.
4 Correct 18 ms 4244 KB Correct.
5 Correct 25 ms 1228 KB Correct.
6 Correct 27 ms 1380 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 1932 KB Correct.
2 Correct 39 ms 1524 KB Correct.
3 Correct 2192 ms 26028 KB Correct.
4 Correct 1657 ms 9156 KB Correct.
5 Correct 1259 ms 45892 KB Correct.
6 Correct 550 ms 21208 KB Correct.
7 Correct 1590 ms 7300 KB Correct.
8 Correct 1407 ms 2816 KB Correct.
9 Correct 287 ms 1952 KB Correct.
10 Correct 320 ms 1960 KB Correct.
11 Correct 1293 ms 2616 KB Correct.
12 Correct 326 ms 1924 KB Correct.
13 Correct 305 ms 1792 KB Correct.
14 Correct 1445 ms 10052 KB Correct.
15 Correct 1848 ms 5368 KB Correct.
16 Correct 287 ms 1828 KB Correct.
17 Correct 367 ms 2080 KB Correct.
18 Correct 376 ms 1944 KB Correct.
19 Correct 1146 ms 2820 KB Correct.
20 Correct 24 ms 488 KB Correct.
21 Correct 27 ms 1008 KB Correct.
22 Correct 34 ms 2164 KB Correct.

Subtask #8
0.0 / 3.0

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