Submission #969478

#	Time	Username	Problem	Language	Result	Execution time	Memory
969478		Turkhuu	Factories (JOI14_factories)	C++17	15 / 100	8015 ms	79292 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<vector<array<int, 2>>> adj;
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    adj.resize(N);
    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]});
    }
}
ll Query(int S, int X[], int T, int Y[]) {
    vector<ll> dis(N, -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 0; i < S; i++) {
        pq.emplace(0, X[i]);
    }
    while (!pq.empty()) {
        auto [s, x] = pq.top();
        pq.pop();
        if (dis[x] != -1) continue;
        dis[x] = s;
        for (auto [y, z] : adj[x]) {
            pq.emplace(s + z, y);
        }
    }
    ll ans = 1e18;
    for (int j = 0; j < T; j++) {
        ans = min(ans, dis[Y[j]]);
    }
    return ans;
}

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