제출 #825748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825748		KoD	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	178 ms	67012 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3