Submission #807525

#	Time	Username	Problem	Language	Result	Execution time	Memory
807525		dong_liu	Cyberland (APIO23_cyberland)	C++17	100 / 100	1803 ms	16664 KiB

cyberland

#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 / 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