Submission #1305065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305065		lsjo	공장들 (JOI14_factories)	C++20	15 / 100	4135 ms	50708 KiB

factories

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

vector<pair<int,int>> graph[500005];
long long dist[500005];

const long long inf = 1e18;

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

  for (int i = 0; i <= N; i++) dist[i]=inf;
}

long long Query(int S, int X[], int T, int Y[]) {
  for (int i = 0; i <= 5005; i++) dist[i]=inf;
  set<pair<long long,int>> to_visit;
  for (int i = 0; i < S; i++) {
    to_visit.insert({0, X[i]});
    //cout << "inserting " << X[i] << "\n";
  }

  while (! to_visit.empty()) {
    auto node = *to_visit.begin();
    to_visit.erase(node);

    if (dist[node.second] <= node.first) continue;
    dist[node.second]=node.first;

    //cout << "visiting " << node.second << " at " << node.first << "\n";

    for (auto x : graph[node.second]) {
      if (node.first+x.second < dist[x.first]) {
        to_visit.insert({node.first+x.second, x.first});
        //cout << "inserting to " << x.first << "\n";
      }
    }
  }

  long long mindist=inf;

  for (int i = 0; i < T; i++) {
    mindist=min(mindist, dist[Y[i]]);
  }

  return mindist;
}

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