Submission #566641

#	Time	Username	Problem	Language	Result	Execution time	Memory
566641		SSRS	Factories (JOI14_factories)	C++14	15 / 100	8053 ms	66204 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const long long INF = 1000000000000000;
vector<vector<pair<int, int>>> E;
void Init(int N, int A[], int B[], int D[]){
  E = vector<vector<pair<int, int>>>(N);
  for (int i = 0; i < N - 1; i++){
    E[A[i]].push_back(make_pair(D[i], B[i]));
    E[B[i]].push_back(make_pair(D[i], A[i]));
  }
}
long long Query(int S, int X[], int T, int Y[]){
  int N = E.size();
  vector<long long> d(N, -1);
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  for (int i = 0; i < S; i++){
    pq.push(make_pair(0, X[i]));
  }
  while (!pq.empty()){
    long long c = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if (d[v] == -1){
      d[v] = c;
      for (auto P : E[v]){
        int w = P.second;
        if (d[w] == -1){
          pq.push(make_pair(c + P.first, w));
        }
      }
    }
  }
  long long ans = INF;
  for (int i = 0; i < T; i++){
    ans = min(ans, d[Y[i]]);
  }
  return ans;
}

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