oj.uz

Submission #970930

# Submission time Handle Problem Language Result Execution time Memory
970930 2024-04-27T14:21:43 Z mannshah1211 Cyberland (APIO23_cyberland) C++17
97 / 100
 1275 ms 59948 KB 
#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;

using state = tuple<double, int, int>;

const double eps = 1e-9;
const double inf = 1e14;

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
  k = min(k, 60);
  vector<vector<double>> d(n, vector<double>(k + 1, inf));
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    g[x[i]].push_back(make_pair(y[i], c[i]));
    g[y[i]].push_back(make_pair(x[i], c[i]));
  }
  d[0][0] = 0;
  priority_queue<state, vector<state>, greater<state>> pq;
  pq.push({0, 0, 0});
  while (!pq.empty()) {
    auto [expected, who, used] = pq.top();
    pq.pop();
    if (d[who][used] - expected < -eps) {
      continue;
    }
    if (who == h) {
      continue;
    }
    for (auto [to, w] : g[who]) {
      if (a[to] == 1) {
        if (d[to][used] > expected + w) {
          d[to][used] = expected + w;
          pq.push({d[to][used], to, used});
        }
      } else if (a[to] == 2) {
        if (used <= k - 1 && d[to][used + 1] > ((expected + (double) w) / 2)) {
          d[to][used + 1] = (expected + (double) w) / 2;
          pq.push({d[to][used + 1], to, used + 1});
        }
        if (d[to][used] > expected + w) {
          d[to][used] = expected + w;
          pq.push({d[to][used], to, used});
        }
      } else {
        if (d[to][used] > 0) {
          d[to][used] = 0;
          pq.push({0, to, used});
        }
      }
    }
  }
  double cur = d[h][0];
  for (int i = 0; i <= k; i++) {
    if (cur > d[h][i]) {
      cur = d[h][i];
    }
  }
  if (abs(cur - inf) < eps) {
    return -1;
  }
  return cur;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 600 KB Correct.
2 Correct 18 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 856 KB Correct.
2 Correct 25 ms 852 KB Correct.
3 Correct 23 ms 824 KB Correct.
4 Correct 25 ms 600 KB Correct.
5 Correct 25 ms 816 KB Correct.
6 Correct 21 ms 4000 KB Correct.
7 Correct 27 ms 4000 KB Correct.
8 Correct 14 ms 7516 KB Correct.
9 Correct 23 ms 348 KB Correct.
10 Correct 23 ms 544 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 604 KB Correct.
2 Correct 26 ms 600 KB Correct.
3 Correct 24 ms 856 KB Correct.
4 Correct 26 ms 344 KB Correct.
5 Correct 27 ms 348 KB Correct.
6 Correct 6 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 21424 KB Correct.
2 Correct 452 ms 600 KB Correct.
3 Correct 400 ms 824 KB Correct.
4 Correct 415 ms 852 KB Correct.
5 Correct 290 ms 544 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 856 KB Correct.
2 Correct 23 ms 604 KB Correct.
3 Correct 23 ms 604 KB Correct.
4 Correct 22 ms 3676 KB Correct.
5 Correct 26 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB Correct.
2 Correct 21 ms 600 KB Correct.
3 Correct 43 ms 27996 KB Correct.
4 Correct 15 ms 2488 KB Correct.
5 Correct 27 ms 348 KB Correct.
6 Correct 23 ms 836 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 1204 KB Correct.
2 Correct 28 ms 1496 KB Correct.
3 Correct 1275 ms 27516 KB Correct.
4 Correct 982 ms 7156 KB Correct.
5 Correct 664 ms 33720 KB Correct.
6 Correct 282 ms 16804 KB Correct.
7 Correct 999 ms 7072 KB Correct.
8 Correct 955 ms 1876 KB Correct.
9 Correct 222 ms 1316 KB Correct.
10 Correct 249 ms 1500 KB Correct.
11 Correct 895 ms 1044 KB Correct.
12 Correct 240 ms 1184 KB Correct.
13 Correct 240 ms 1672 KB Correct.
14 Correct 881 ms 9064 KB Correct.
15 Correct 1168 ms 2780 KB Correct.
16 Correct 222 ms 1252 KB Correct.
17 Correct 276 ms 1436 KB Correct.
18 Correct 278 ms 1204 KB Correct.
19 Correct 829 ms 1612 KB Correct.
20 Correct 18 ms 600 KB Correct.
21 Correct 26 ms 1060 KB Correct.
22 Correct 20 ms 2260 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 2408 KB Correct.
2 Correct 61 ms 2652 KB Correct.
3 Incorrect 468 ms 59948 KB Wrong Answer.
4 Halted 0 ms 0 KB -