Submission #942935

#	Time	Username	Problem	Language	Result	Execution time	Memory
942935		kunzaZa183	Cyberland (APIO23_cyberland)	C++17	0 / 100	27 ms	6988 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

struct state
{
  int weight, node;
  friend bool operator<(state a, state x)
  {
    return a.weight > x.weight;
  }
};

vector<double> dp;
vector<vector<pair<int, int>>> adjlist;
vector<int> type;
vector<bool> visited;
vector<int> zeroes;
int target;

void recur2sub3(int node, double len)
{
  visited[node] = 1;
  if (type[node] == 0)
  {
    zeroes.push_back(node);
    return;
  }
  for (auto a : adjlist[node])
    if (!visited[a.first])
      recur2sub3(a.first, len + a.second);
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
  target = H;
  type = arr;
  dp.clear();
  adjlist.clear(), zeroes.clear(), visited.clear();
  visited.resize(N, 0), adjlist.resize(N);
  for (int i = 0; i < M; i++)
    adjlist[x[i]].push_back({ y[i], c[i] }), adjlist[y[i]].push_back({ x[i], c[i] });
  dp.resize(N, 1e15);
  recur2sub3(H, 0);
  priority_queue<state> pqs;
  pqs.push({ 0, H });
  while (!pqs.empty())
  {
    state tmp = pqs.top();
    pqs.pop();
    if (tmp.weight < dp[tmp.node])
    {
      dp[tmp.node] = tmp.weight;
      for (auto a : adjlist[tmp.node])
        if (tmp.weight + a.second < dp[a.first])
          pqs.push({ tmp.weight + a.second, a.first });
    }
  }
  double mini = dp[0];
  for (auto a : zeroes)
    mini = min(mini, dp[a]);
  return mini;
}

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