oj.uz

Submission #1053074

# Submission time Handle Problem Language Result Execution time Memory
1053074 2024-08-11T08:30:45 Z manhlinh1501 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 77596 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29532 KB Output is correct
2 Correct 1828 ms 43148 KB Output is correct
3 Correct 1807 ms 43092 KB Output is correct
4 Correct 1325 ms 43288 KB Output is correct
5 Correct 916 ms 43000 KB Output is correct
6 Correct 2048 ms 43320 KB Output is correct
7 Correct 1806 ms 43136 KB Output is correct
8 Correct 1670 ms 43088 KB Output is correct
9 Correct 978 ms 43020 KB Output is correct
10 Correct 2055 ms 43316 KB Output is correct
11 Correct 1774 ms 43140 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29272 KB Output is correct
2 Execution timed out 8085 ms 77596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29532 KB Output is correct
2 Correct 1828 ms 43148 KB Output is correct
3 Correct 1807 ms 43092 KB Output is correct
4 Correct 1325 ms 43288 KB Output is correct
5 Correct 916 ms 43000 KB Output is correct
6 Correct 2048 ms 43320 KB Output is correct
7 Correct 1806 ms 43136 KB Output is correct
8 Correct 1670 ms 43088 KB Output is correct
9 Correct 978 ms 43020 KB Output is correct
10 Correct 2055 ms 43316 KB Output is correct
11 Correct 1774 ms 43140 KB Output is correct
12 Correct 15 ms 29272 KB Output is correct
13 Execution timed out 8085 ms 77596 KB Time limit exceeded
14 Halted 0 ms 0 KB -