oj.uz

Submission #883310

# Submission time Handle Problem Language Result Execution time Memory
883310 2023-12-05T06:38:30 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 4224 ms 56148 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 + 0, 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16988 KB Output is correct
2 Correct 4157 ms 31016 KB Output is correct
3 Correct 4069 ms 31128 KB Output is correct
4 Correct 3156 ms 31372 KB Output is correct
5 Correct 2258 ms 31440 KB Output is correct
6 Correct 4224 ms 31392 KB Output is correct
7 Correct 4010 ms 30880 KB Output is correct
8 Correct 3799 ms 31416 KB Output is correct
9 Correct 2250 ms 31188 KB Output is correct
10 Correct 4144 ms 31152 KB Output is correct
11 Correct 3984 ms 31064 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16984 KB Output is correct
2 Runtime error 214 ms 56148 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16988 KB Output is correct
2 Correct 4157 ms 31016 KB Output is correct
3 Correct 4069 ms 31128 KB Output is correct
4 Correct 3156 ms 31372 KB Output is correct
5 Correct 2258 ms 31440 KB Output is correct
6 Correct 4224 ms 31392 KB Output is correct
7 Correct 4010 ms 30880 KB Output is correct
8 Correct 3799 ms 31416 KB Output is correct
9 Correct 2250 ms 31188 KB Output is correct
10 Correct 4144 ms 31152 KB Output is correct
11 Correct 3984 ms 31064 KB Output is correct
12 Correct 34 ms 16984 KB Output is correct
13 Runtime error 214 ms 56148 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -