oj.uz

Submission #969472

# Submission time Handle Problem Language Result Execution time Memory
969472 2024-04-25T08:26:02 Z Turkhuu Factories (JOI14_factories) C++17
0 / 100
 8000 ms 79648 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 17092 KB Output is correct
2 Execution timed out 8010 ms 30548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 16920 KB Output is correct
2 Execution timed out 8020 ms 79648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 17092 KB Output is correct
2 Execution timed out 8010 ms 30548 KB Time limit exceeded
3 Halted 0 ms 0 KB -