oj.uz

Submission #825748

# Submission time Handle Problem Language Result Execution time Memory
825748 2023-08-15T07:38:24 Z KoD Cyberland (APIO23_cyberland) C++17
100 / 100
 178 ms 67012 KB 
#include "cyberland.h"

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

struct union_find {
  explicit union_find(int n) : data(n, -1) {}

  int find(int u) { return data[u] < 0 ? u : data[u] = find(data[u]); }
  bool same(int x, int y) { return find(x) == find(y); }

  void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }

 private:
  vector<int> data;
};

double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> A) {
  constexpr int MaxK = 70;
  K = std::min(K, MaxK - 1);
  union_find dsu(N);
  vector<int> Z(M);
  vector<vector<int>> G(N);
  for (int i = 0; i < M; ++i) {
    Z[i] = X[i] ^ Y[i];
    G[X[i]].push_back(i);
    G[Y[i]].push_back(i);
    if (X[i] != H && Y[i] != H) dsu.merge(X[i], Y[i]);
  }
  array<double, MaxK> pow;
  pow[0] = 1;
  for (int i = 1; i < MaxK; ++i) {
    pow[i] = pow[i - 1] * 0.5;
  }
  vector<array<double, MaxK>> dist(N);
  for (auto& a : dist) a.fill(1e16);
  struct Info {
    int u, k;
    double d;
    bool operator<(const Info& t) const { return d > t.d; }
  };
  std::priority_queue<Info> heap;
  const auto push = [&](int u, int k, double d) {
    if (dist[u][k] > d) {
      dist[u][k] = d;
      heap.push({u, k, d});
    }
  };
  A[0] = 0;
  push(H, K, 0);
  while (!heap.empty()) {
    const auto [u, k, d] = heap.top();
    heap.pop();
    if (dist[u][k] < d) continue;
    if (A[u] == 0) return d;
    for (const int e : G[u]) {
      const int v = Z[e] ^ u;
      if (!dsu.same(0, v)) continue;
      push(v, k, d + C[e] * pow[K - k]);
      if (A[u] == 2 && k > 0) push(v, k - 1, d + C[e] * pow[K - k + 1]);
    }
  }
  return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 428 KB Correct.
2 Correct 18 ms 724 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1500 KB Correct.
2 Correct 27 ms 1480 KB Correct.
3 Correct 22 ms 1388 KB Correct.
4 Correct 23 ms 1412 KB Correct.
5 Correct 23 ms 1436 KB Correct.
6 Correct 22 ms 10572 KB Correct.
7 Correct 28 ms 7880 KB Correct.
8 Correct 14 ms 12820 KB Correct.
9 Correct 23 ms 480 KB Correct.
10 Correct 22 ms 456 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1512 KB Correct.
2 Correct 21 ms 1188 KB Correct.
3 Correct 20 ms 1516 KB Correct.
4 Correct 23 ms 340 KB Correct.
5 Correct 22 ms 436 KB Correct.
6 Correct 5 ms 5460 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 37604 KB Correct.
2 Correct 23 ms 2492 KB Correct.
3 Correct 26 ms 2388 KB Correct.
4 Correct 21 ms 2240 KB Correct.
5 Correct 23 ms 1440 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1460 KB Correct.
2 Correct 24 ms 1508 KB Correct.
3 Correct 24 ms 1540 KB Correct.
4 Correct 24 ms 6448 KB Correct.
5 Correct 21 ms 432 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1420 KB Correct.
2 Correct 19 ms 968 KB Correct.
3 Correct 56 ms 48592 KB Correct.
4 Correct 16 ms 4356 KB Correct.
5 Correct 22 ms 428 KB Correct.
6 Correct 22 ms 1232 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1372 KB Correct.
2 Correct 4 ms 1464 KB Correct.
3 Correct 70 ms 63588 KB Correct.
4 Correct 55 ms 28912 KB Correct.
5 Correct 41 ms 26580 KB Correct.
6 Correct 26 ms 10936 KB Correct.
7 Correct 51 ms 16612 KB Correct.
8 Correct 45 ms 4932 KB Correct.
9 Correct 21 ms 2164 KB Correct.
10 Correct 26 ms 1880 KB Correct.
11 Correct 51 ms 3372 KB Correct.
12 Correct 23 ms 2272 KB Correct.
13 Correct 22 ms 2020 KB Correct.
14 Correct 61 ms 31468 KB Correct.
15 Correct 47 ms 12004 KB Correct.
16 Correct 23 ms 2080 KB Correct.
17 Correct 24 ms 2452 KB Correct.
18 Correct 23 ms 2548 KB Correct.
19 Correct 43 ms 3380 KB Correct.
20 Correct 3 ms 468 KB Correct.
21 Correct 3 ms 1004 KB Correct.
22 Correct 3 ms 1364 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1328 KB Correct.
2 Correct 4 ms 1468 KB Correct.
3 Correct 92 ms 67012 KB Correct.
4 Correct 47 ms 10452 KB Correct.
5 Correct 45 ms 26616 KB Correct.
6 Correct 26 ms 10936 KB Correct.
7 Correct 55 ms 29096 KB Correct.
8 Correct 47 ms 3344 KB Correct.
9 Correct 24 ms 2144 KB Correct.
10 Correct 21 ms 1924 KB Correct.
11 Correct 178 ms 1624 KB Correct.
12 Correct 23 ms 2096 KB Correct.
13 Correct 22 ms 2052 KB Correct.
14 Correct 53 ms 27064 KB Correct.
15 Correct 62 ms 33924 KB Correct.
16 Correct 56 ms 17988 KB Correct.
17 Correct 46 ms 5924 KB Correct.
18 Correct 23 ms 2088 KB Correct.
19 Correct 24 ms 2420 KB Correct.
20 Correct 23 ms 2540 KB Correct.
21 Correct 44 ms 3384 KB Correct.
22 Correct 3 ms 468 KB Correct.
23 Correct 2 ms 980 KB Correct.
24 Correct 3 ms 1364 KB Correct.