Submission #1053074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053074		manhlinh1501	Factories (JOI14_factories)	C++17	15 / 100	8085 ms	77596 KiB

factories

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 5e5 + 5;
const i64 oo64 = 1e18;
using pli = pair<i64, int>;
int N, Q;
vector<pii> adj[MAXN];

void Init(int _N, int A[], int B[], int D[]) {
    N = _N;
    for(int i = 0; i < N - 1; i++) {
        int u = A[i];
        int v = B[i];
        int w = D[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
}

i64 Query(int S, int X[], int T, int Y[]) {
    vector<i64> dist(N, oo64);
    priority_queue<pli, vector<pli>, greater<pli>> Q;
    for(int i = 0; i < S; i++) {
        int u = X[i];
        dist[u] = 0;
        Q.emplace(dist[u], u);
    }
    while(!Q.empty()) {
        pli top = Q.top();
        Q.pop();
        int u = top.second;
        if(top.first != dist[u]) continue;
        for(pii _ : adj[u]) {
            int v = _.first;
            int w = _.second;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                Q.emplace(dist[v], v);
            }
        }
    }
    i64 ans = oo64;
    for(int i = 0; i < T; i++) {
        int u = Y[i];
        ans = min(ans, dist[u]);
    }
    return ans;
}

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