Submission #773858

#	Time	Username	Problem	Language	Result	Execution time	Memory
773858		peijar	Cyberland (APIO23_cyberland)	C++17	100 / 100	2474 ms	17496 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const double INF = 1e18;
template <typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>;

double solve(signed nbSommets, signed nbAretes, signed maxDiv, signed arrival,
             vector<signed> x, vector<signed> y, vector<signed> cost,
             vector<signed> effect) {
  vector<vector<pair<int, int>>> adj(nbSommets);
  for (int i = 0; i < nbAretes; ++i) {
    adj[x[i]].emplace_back(y[i], cost[i]);
    adj[y[i]].emplace_back(x[i], cost[i]);
  }
  dbg(maxDiv, arrival);
  dbg(x);
  dbg(y);
  dbg(cost);
  dbg(effect);

  vector<bool> reachable(nbSommets);
  reachable[0] = true;
  queue<int> q;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == arrival)
      continue;
    for (auto [v, c] : adj[u])
      if (!reachable[v]) {
        reachable[v] = true;
        q.push(v);
      }
  }

  maxDiv = min(maxDiv, 100);
  vector<double> curDis(nbSommets, INF);
  curDis[0] = 0;
  for (int u = 0; u < nbSommets; ++u)
    if (reachable[u] and effect[u] == 0)
      curDis[u] = 0;

  for (int iter = 0; iter <= maxDiv; ++iter) {
    min_pq<pair<double, int>> pq;
    for (int u = 0; u < nbSommets; ++u)
      if (curDis[u] < INF)
        pq.emplace(curDis[u], u);
    vector<double> nxtDis(nbSommets, INF);
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (u == arrival)
        continue;
      if (d > nxtDis[u])
        continue;
      for (auto [v, c] : adj[u])
        if (d + c < nxtDis[v]) {
          nxtDis[v] = d + c;
          pq.emplace(nxtDis[v], v);
        }
    }
    dbg(curDis);
    for (int u = 0; u < nbSommets; ++u) {
      curDis[u] = min(curDis[u], nxtDis[u]);
      if (iter < maxDiv and effect[u] == 2 and nxtDis[u] < INF)
        curDis[u] = min(curDis[u], nxtDis[u] / 2);
    }
  }
  return curDis[arrival] == INF ? -1 : curDis[arrival];
}

• 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