oj.uz

Submission #969478

# Submission time Handle Problem Language Result Execution time Memory
969478 2024-04-25T08:28:22 Z Turkhuu Factories (JOI14_factories) C++17
15 / 100
 8000 ms 79292 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[]) {
    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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16996 KB Output is correct
2 Correct 4567 ms 30888 KB Output is correct
3 Correct 4388 ms 31080 KB Output is correct
4 Correct 3358 ms 31324 KB Output is correct
5 Correct 2283 ms 31084 KB Output is correct
6 Correct 4968 ms 31260 KB Output is correct
7 Correct 4386 ms 31060 KB Output is correct
8 Correct 4086 ms 31068 KB Output is correct
9 Correct 2294 ms 31344 KB Output is correct
10 Correct 4973 ms 31292 KB Output is correct
11 Correct 4505 ms 31052 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16732 KB Output is correct
2 Execution timed out 8015 ms 79292 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16996 KB Output is correct
2 Correct 4567 ms 30888 KB Output is correct
3 Correct 4388 ms 31080 KB Output is correct
4 Correct 3358 ms 31324 KB Output is correct
5 Correct 2283 ms 31084 KB Output is correct
6 Correct 4968 ms 31260 KB Output is correct
7 Correct 4386 ms 31060 KB Output is correct
8 Correct 4086 ms 31068 KB Output is correct
9 Correct 2294 ms 31344 KB Output is correct
10 Correct 4973 ms 31292 KB Output is correct
11 Correct 4505 ms 31052 KB Output is correct
12 Correct 49 ms 16732 KB Output is correct
13 Execution timed out 8015 ms 79292 KB Time limit exceeded
14 Halted 0 ms 0 KB -