Submission #871765

#	Time	Username	Problem	Language	Result	Execution time	Memory
871765		vjudge1	Cyberland (APIO23_cyberland)	C++17	44 / 100	40 ms	9812 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);
  vector < ll > eda (n, -1);
  q.push ({ 0ll, h });
  while (q.size ())
    {
      auto x = q.top ();
      q.pop ();
      if (eda[x.second] != -1) continue;
      eda[x.second] = -x.first;
      for (auto &y : adj[x.second])
        q.push ({ x.first - y.first, y.second });
    }
  double ans = 1e18;
  for (auto &x : rz) ans = min (ans, (double) eda[x]);
  // vector < ll > dda (n, -1);
  // vector < ll > bfd (n, (ll) 1e18);
  // priority_queue < pair < ll, pair < int, int > > > pq;
  // for (auto &x : rd) pq.insert ({ 0ll, make_pair (x, x) });
  // while (pq.size ())
  //   {
  //     auto x = q.top ();
  //     q.pop ();
  //     if (x.second.first == h) continue;
  //     if (dda[x.second.first] == -1 || dda[x.second.first] == -x.first)
  //       bfd[x.second.second] = min (bfd[x.second.second], -x.first);
  //     if (dda[x.second.first] != -1) continue;
  //     dda[x.second.first] = -x.first;
  //     for (auto &y : adj[x.second.first])
  //       q.push ({ x.first - y.first, make_pair (y.second, x.second.first) });
  //   }
  // for (auto &x : rd)
  //   {
  //     bfd[x]
  //   }
  return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3