oj.uz

Submission #807525

# Submission time Handle Problem Language Result Execution time Memory
807525 2023-08-04T18:59:08 Z dong_liu Cyberland (APIO23_cyberland) C++17
100 / 100
 1803 ms 16664 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 55 ms 856 KB Correct.
2 Correct 49 ms 656 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1312 KB Correct.
2 Correct 162 ms 1480 KB Correct.
3 Correct 154 ms 1468 KB Correct.
4 Correct 166 ms 1484 KB Correct.
5 Correct 170 ms 1464 KB Correct.
6 Correct 206 ms 2588 KB Correct.
7 Correct 271 ms 2460 KB Correct.
8 Correct 119 ms 3720 KB Correct.
9 Correct 83 ms 1256 KB Correct.
10 Correct 91 ms 1272 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 1448 KB Correct.
2 Correct 167 ms 1324 KB Correct.
3 Correct 151 ms 1380 KB Correct.
4 Correct 93 ms 1256 KB Correct.
5 Correct 92 ms 1260 KB Correct.
6 Correct 49 ms 1628 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 8176 KB Correct.
2 Correct 101 ms 1452 KB Correct.
3 Correct 99 ms 1432 KB Correct.
4 Correct 93 ms 1432 KB Correct.
5 Correct 68 ms 1392 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1336 KB Correct.
2 Correct 72 ms 1424 KB Correct.
3 Correct 81 ms 1488 KB Correct.
4 Correct 117 ms 2056 KB Correct.
5 Correct 52 ms 1204 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1444 KB Correct.
2 Correct 67 ms 1332 KB Correct.
3 Correct 37 ms 9732 KB Correct.
4 Correct 78 ms 1780 KB Correct.
5 Correct 60 ms 1268 KB Correct.
6 Correct 83 ms 1344 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1336 KB Correct.
2 Correct 16 ms 596 KB Correct.
3 Correct 610 ms 16088 KB Correct.
4 Correct 442 ms 5608 KB Correct.
5 Correct 386 ms 8828 KB Correct.
6 Correct 183 ms 5640 KB Correct.
7 Correct 411 ms 4768 KB Correct.
8 Correct 325 ms 2696 KB Correct.
9 Correct 85 ms 1340 KB Correct.
10 Correct 86 ms 1336 KB Correct.
11 Correct 267 ms 2408 KB Correct.
12 Correct 95 ms 1460 KB Correct.
13 Correct 91 ms 1480 KB Correct.
14 Correct 336 ms 8348 KB Correct.
15 Correct 357 ms 3952 KB Correct.
16 Correct 87 ms 1408 KB Correct.
17 Correct 109 ms 1436 KB Correct.
18 Correct 117 ms 1480 KB Correct.
19 Correct 342 ms 2320 KB Correct.
20 Correct 8 ms 340 KB Correct.
21 Correct 7 ms 456 KB Correct.
22 Correct 14 ms 852 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 1396 KB Correct.
2 Correct 40 ms 596 KB Correct.
3 Correct 1619 ms 16664 KB Correct.
4 Correct 488 ms 3348 KB Correct.
5 Correct 1157 ms 8828 KB Correct.
6 Correct 515 ms 5680 KB Correct.
7 Correct 738 ms 7936 KB Correct.
8 Correct 405 ms 2600 KB Correct.
9 Correct 200 ms 1428 KB Correct.
10 Correct 192 ms 1280 KB Correct.
11 Correct 278 ms 1532 KB Correct.
12 Correct 224 ms 1432 KB Correct.
13 Correct 213 ms 1484 KB Correct.
14 Correct 1413 ms 8336 KB Correct.
15 Correct 1803 ms 9264 KB Correct.
16 Correct 690 ms 4396 KB Correct.
17 Correct 495 ms 2696 KB Correct.
18 Correct 226 ms 1484 KB Correct.
19 Correct 265 ms 1540 KB Correct.
20 Correct 236 ms 1484 KB Correct.
21 Correct 973 ms 2336 KB Correct.
22 Correct 13 ms 340 KB Correct.
23 Correct 14 ms 436 KB Correct.
24 Correct 38 ms 816 KB Correct.