Submission #969472

#	Time	Username	Problem	Language	Result	Execution time	Memory
969472		Turkhuu	Factories (JOI14_factories)	C++17	0 / 100	8020 ms	79648 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[]) {
    ll ans = 1e18;
    for (int i = 0; i < S; i++) {
        vector<ll> dis(N, -1);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        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);
            }
        }
        for (int j = 0; j < T; j++) {
            ans = min(ans, dis[Y[j]]);
        }
    }
    return ans;
}

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