oj.uz

Submission #970922

# Submission time Handle Problem Language Result Execution time Memory
970922 2024-04-27T14:16:15 Z mannshah1211 Cyberland (APIO23_cyberland) C++17
97 / 100
 1344 ms 2097152 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) {
  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 22 ms 600 KB Correct.
2 Correct 18 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 856 KB Correct.
2 Correct 25 ms 800 KB Correct.
3 Correct 23 ms 856 KB Correct.
4 Correct 24 ms 808 KB Correct.
5 Correct 24 ms 820 KB Correct.
6 Correct 21 ms 3860 KB Correct.
7 Correct 27 ms 4000 KB Correct.
8 Correct 13 ms 7516 KB Correct.
9 Correct 23 ms 560 KB Correct.
10 Correct 23 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 600 KB Correct.
2 Correct 25 ms 600 KB Correct.
3 Correct 24 ms 860 KB Correct.
4 Correct 25 ms 568 KB Correct.
5 Correct 28 ms 600 KB Correct.
6 Correct 6 ms 3380 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 21332 KB Correct.
2 Correct 466 ms 1044 KB Correct.
3 Correct 377 ms 832 KB Correct.
4 Correct 406 ms 848 KB Correct.
5 Correct 285 ms 348 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Correct.
2 Correct 23 ms 1884 KB Correct.
3 Correct 23 ms 1864 KB Correct.
4 Correct 22 ms 4472 KB Correct.
5 Correct 21 ms 1560 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Correct.
2 Correct 21 ms 1572 KB Correct.
3 Correct 44 ms 29808 KB Correct.
4 Correct 15 ms 3252 KB Correct.
5 Correct 24 ms 1372 KB Correct.
6 Correct 23 ms 1628 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 1236 KB Correct.
2 Correct 28 ms 1664 KB Correct.
3 Correct 1344 ms 29864 KB Correct.
4 Correct 995 ms 9664 KB Correct.
5 Correct 630 ms 34488 KB Correct.
6 Correct 255 ms 18868 KB Correct.
7 Correct 982 ms 8848 KB Correct.
8 Correct 943 ms 3312 KB Correct.
9 Correct 219 ms 2300 KB Correct.
10 Correct 237 ms 2388 KB Correct.
11 Correct 888 ms 2800 KB Correct.
12 Correct 239 ms 2188 KB Correct.
13 Correct 247 ms 2244 KB Correct.
14 Correct 840 ms 10636 KB Correct.
15 Correct 1154 ms 4988 KB Correct.
16 Correct 234 ms 2176 KB Correct.
17 Correct 282 ms 2336 KB Correct.
18 Correct 280 ms 2468 KB Correct.
19 Correct 842 ms 3736 KB Correct.
20 Correct 18 ms 600 KB Correct.
21 Correct 20 ms 1116 KB Correct.
22 Correct 21 ms 2260 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 735 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -