Submission #872314

#	Time	Username	Problem	Language	Result	Execution time	Memory
872314		AkibAzmain	Cyberland (APIO23_cyberland)	C++17	100 / 100	2990 ms	74068 KiB

cyberland

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

double
solve (int n, int m, int k, int h,
       std::vector<int> x, std::vector<int> y, std::vector<int> c,
       std::vector<int> arr)
{
  vector < vector < pair < int, int > > > adj (n);
  for (int i = 0; i < m; ++i)
    {
      adj[x[i]].push_back ({ c[i], y[i] });
      adj[y[i]].push_back ({ c[i], x[i] });
    }
  priority_queue < pair < ll, int > > q;
  q.push ({ 0ll, 0 });
  vector < ll > sda (n, -1);
  while (q.size ())
    {
      auto x = q.top ();
      q.pop ();
      if (sda[x.second] != -1) continue;
      sda[x.second] = -x.first;
      if (x.second == h) continue;
      for (auto &y : adj[x.second])
        q.push ({ x.first - y.first, y.second });
    }
  if (sda[h] == -1) return -1;
  set < int > rz;
  rz.insert (0);
  for (int i = 0; i < n; ++i)
    if (arr[i] == 0 && sda[i] > 0)
      rz.insert (i);
  set < int > rd;
  for (int i = 0; i < n; ++i)
    if (arr[i] == 2 && sda[i] > 0)
      rd.insert (i);
  k = min (k, 80);
  vector < vector < double > > da (k + 1, vector < double > (n, -1));
  double ans = 1e18;
  for (ll i = 0; i <= k; ++i)
    {
      priority_queue < pair < double, int > > pq;
      if (!i)
        for (auto &x : rz)
          pq.push ({ (double) 0, x });
      else
        for (auto &x : rd)
          for (auto &y : adj[x])
            pq.push ({ (double) -da[i - 1][x] / 2 - y.first, y.second });
      while (pq.size ())
        {
          auto x = pq.top ();
          pq.pop ();
          if (da[i][x.second] >= -0.5) continue;
          da[i][x.second] = -x.first;
          if (x.second == h) continue;
          for (auto &y : adj[x.second])
            pq.push ({ (double) x.first - y.first, y.second });
        }
      if (da[i][h] >= -0.5)
        ans = min (ans, da[i][h]);
    }
  return ans;
}

• 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