Submission #1014245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014245		adrielcp	Factories (JOI14_factories)	C++17	15 / 100	8068 ms	80240 KiB

factories

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

#define ll long long
const ll INF = 1e18;
#define info pair<ll,ll>
vector<vector<info>> adj;
int n;

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  adj = vector<vector<info>>(n, vector<info>());
  for (int i = 0; i < n-1; i++) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }
}

long long Query(int s, int X[], int t, int Y[]) {
  priority_queue<info, vector<info>, greater<info>> pq;
  for (int i = 0; i < s; i++) pq.push({0, X[i]});

  vector<ll> dist(n,INF); // closest dist to any X

  while (!pq.empty()) {
    auto [cost, node] = pq.top();pq.pop();
    if (cost > dist[node]) continue;
    dist[node] = cost;
    for (auto [children, w] : adj[node]) {
      if (cost+w < dist[children]) {
        dist[children] = cost+w;
        pq.push({cost+w, children});
      }
    }
  }

  ll ans = INF;
  for (int i = 0; i < t; i++) {
    // cout << dist[Y[i]] << " t" << endl;
    ans = min(ans, dist[Y[i]]);
  }

  return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67