oj.uz

Submission #883308

# Submission time Handle Problem Language Result Execution time Memory
883308 2023-12-05T06:28:21 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 48 ms 17212 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;

const int N = 5000;

int n, q;
ll dis[N + 10];
vector<pair<int, ll>> adj[N + 10];
vector<int> vec1, vec2;

void Init(int N, int A[], int B[], int D[]) {
    n = 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]});
    }
}

void dij() {
    fill(dis + 1, dis + n + 1, INF);
    set<pair<ll, int>> st;
    for (auto t: vec1) {
        dis[t] = 0;
        st.insert({0, t});
    }
    while (!st.empty()) {
        int u = st.begin() -> second;
        st.erase(st.begin());
        for (auto [v, w]: adj[u])
            if (dis[u] + w < dis[v]) {
                st.erase({dis[v], v});
                dis[v] = dis[u] + w;
                st.insert({dis[v], v});
            }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) 
        vec1.push_back(X[i]);
    for (int i = 0; i < T; i++)
        vec2.push_back(Y[i]);
    dij();
    ll mn = INF;
    for (auto t: vec2)
        mn = min(mn, dis[t]);
    vec1.clear();
    vec2.clear();
    return mn;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 17212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 17212 KB Output isn't correct
2 Halted 0 ms 0 KB -