Submission #422352

#	Time	Username	Problem	Language	Result	Execution time	Memory
422352		tengiz05	Factories (JOI14_factories)	C++17	15 / 100	8055 ms	54484 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000;
std::vector<std::pair<int, i64>> e[N];
int n;
void Init(int n, int A[], int B[], int D[]) {
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].emplace_back(B[i], D[i]);
        e[B[i]].emplace_back(A[i], D[i]);
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> q;
    std::vector<i64> dist(n, 1e16);
    for (int i = 0; i < S; i++) {
        q.emplace(0, X[i]);
        dist[X[i]] = 0;
    }
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : e[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                q.emplace(dist[v], v);
            }
        }
    }
    i64 ans =  1e16;
    for (int i = 0; i < T; i++) {
        ans = std::min(ans, dist[Y[i]]);
    }
    return ans;
}

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