oj.uz

Submission #894262

# Submission time Handle Problem Language Result Execution time Memory
894262 2023-12-28T03:09:12 Z box Cyberland (APIO23_cyberland) C++17
100 / 100
 2023 ms 16920 KB 
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
 
typedef vector<int> vi;
 
const double eps = 1e-8;
 
double solve(int n, int m, int k, int e, vi x, vi y, vi c, vi a) {
  vector<vi> g(n);
  for (int h = 0; h < m; h++) {
    g[x[h]].push_back(h);
    g[y[h]].push_back(h);
  }
  vector<bool> alive(n);
  vector<double> d(n);
 
  k = min(k, 100);
 
  auto run = [&]() {
    priority_queue<pair<double, int>> pq;
    for (int i = 0; i < n; i++)
      if (alive[i]) pq.push({-d[i], i});
    while (pq.size()) {
      auto [v, i] = pq.top();
      pq.pop();
      v *= -1;
      if (abs(v - d[i]) > eps) continue;
      if (i == e) continue;
      for (int h : g[i]) {
        int j = i ^ x[h] ^ y[h];
        if (!alive[j]) {
          alive[j] = 1;
          d[j] = a[j] == 0 ? 0 : d[i] + c[h];
          pq.push({-d[j], j});
        } else {
          double nd = a[j] == 0 ? 0 : d[i] + c[h];
          if (nd < d[j] - eps) {
            d[j] = nd;
            pq.push({-d[j], j});
          }
        }
      }
    }
  };
 
  alive[0] = 1, d[0] = 0;
  run();
 
  while (k--) {
    auto nd = d;
    auto nalive = alive;
    for (int i = 0; i < n; i++)
      if (alive[i] && i != e) {
        for (int h : g[i]) {
          int j = i ^ x[h] ^ y[h];
          if (a[j] != 2) continue;
          if (!alive[j]) {
            nalive[j] = 1;
            nd[j] = (d[i] + c[h]) / 2;
          } else {
            nd[j] = min(nd[j], (d[i] + c[h]) / 2);
          }
        }
      }
    d = nd;
    alive = nalive;
    run();
  }
  if (alive[e]) return d[e];
  return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 848 KB Correct.
2 Correct 50 ms 844 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1712 KB Correct.
2 Correct 164 ms 1620 KB Correct.
3 Correct 153 ms 1472 KB Correct.
4 Correct 164 ms 1632 KB Correct.
5 Correct 171 ms 1580 KB Correct.
6 Correct 201 ms 2732 KB Correct.
7 Correct 272 ms 2592 KB Correct.
8 Correct 119 ms 3740 KB Correct.
9 Correct 83 ms 1404 KB Correct.
10 Correct 91 ms 1408 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1584 KB Correct.
2 Correct 169 ms 1584 KB Correct.
3 Correct 159 ms 1340 KB Correct.
4 Correct 100 ms 1392 KB Correct.
5 Correct 104 ms 1876 KB Correct.
6 Correct 45 ms 1628 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8280 KB Correct.
2 Correct 112 ms 1616 KB Correct.
3 Correct 91 ms 1360 KB Correct.
4 Correct 97 ms 1588 KB Correct.
5 Correct 64 ms 1396 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1364 KB Correct.
2 Correct 75 ms 1424 KB Correct.
3 Correct 112 ms 1616 KB Correct.
4 Correct 127 ms 2128 KB Correct.
5 Correct 54 ms 1140 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1556 KB Correct.
2 Correct 78 ms 1468 KB Correct.
3 Correct 54 ms 9716 KB Correct.
4 Correct 75 ms 1924 KB Correct.
5 Correct 88 ms 1360 KB Correct.
6 Correct 80 ms 1460 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1472 KB Correct.
2 Correct 16 ms 604 KB Correct.
3 Correct 831 ms 16372 KB Correct.
4 Correct 462 ms 5728 KB Correct.
5 Correct 433 ms 8968 KB Correct.
6 Correct 236 ms 5920 KB Correct.
7 Correct 449 ms 4876 KB Correct.
8 Correct 352 ms 2820 KB Correct.
9 Correct 105 ms 1820 KB Correct.
10 Correct 94 ms 1332 KB Correct.
11 Correct 283 ms 2416 KB Correct.
12 Correct 98 ms 1580 KB Correct.
13 Correct 95 ms 1528 KB Correct.
14 Correct 352 ms 8476 KB Correct.
15 Correct 349 ms 4088 KB Correct.
16 Correct 125 ms 1416 KB Correct.
17 Correct 125 ms 1624 KB Correct.
18 Correct 146 ms 1876 KB Correct.
19 Correct 378 ms 2460 KB Correct.
20 Correct 6 ms 344 KB Correct.
21 Correct 7 ms 592 KB Correct.
22 Correct 18 ms 952 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 1420 KB Correct.
2 Correct 52 ms 604 KB Correct.
3 Correct 1752 ms 16920 KB Correct.
4 Correct 488 ms 3480 KB Correct.
5 Correct 1359 ms 9408 KB Correct.
6 Correct 586 ms 5836 KB Correct.
7 Correct 808 ms 7912 KB Correct.
8 Correct 423 ms 2608 KB Correct.
9 Correct 235 ms 1340 KB Correct.
10 Correct 195 ms 1364 KB Correct.
11 Correct 278 ms 1724 KB Correct.
12 Correct 225 ms 1604 KB Correct.
13 Correct 212 ms 1508 KB Correct.
14 Correct 1763 ms 8372 KB Correct.
15 Correct 2023 ms 9608 KB Correct.
16 Correct 725 ms 4676 KB Correct.
17 Correct 508 ms 2956 KB Correct.
18 Correct 205 ms 1624 KB Correct.
19 Correct 272 ms 1872 KB Correct.
20 Correct 238 ms 1480 KB Correct.
21 Correct 1012 ms 2332 KB Correct.
22 Correct 14 ms 344 KB Correct.
23 Correct 15 ms 600 KB Correct.
24 Correct 47 ms 1112 KB Correct.