oj.uz

Submission #976297

# Submission time Handle Problem Language Result Execution time Memory
976297 2024-05-06T11:55:30 Z saayan007 Factories (JOI14_factories) C++17
15 / 100
 2510 ms 37460 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const char nl = '\n';

using ll = long long;
#warning checkconstanst as per subtask
const int mxN = 5e3L + 10;

vector<pair<int, ll>> adj[mxN];
int n;

/* void Init(int N, int A[], int B[], int D[]) { */
void Init(signed N, signed A[], signed B[], signed D[]) {
    n = N;
    for(int i = 0; i < N - 1; ++i) {
        adj[A[i]].emplace_back(B[i], ll(D[i]));
        adj[B[i]].emplace_back(A[i], ll(D[i]));
    }
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
    ll dist[n];
    for(int i = 0; i < n; ++i) dist[i] = -1;
    priority_queue<pair<ll, int>> pq;

    for(int i = 0; i < S; ++i) {
        dist[X[i]] = 0;
        pq.emplace(0, X[i]);
    }

    while(!pq.empty()) {
        int a = pq.top().second;
        ll d = -pq.top().first;
        pq.pop();
        if(dist[a] < d) continue;
        for(auto U : adj[a]) {
            int b = U.first; ll w = U.second;
            if(dist[b] == -1 || dist[b] > d + w) {
                dist[b] = d + w;
                pq.emplace(-dist[b], b);
            }
        }
    }
    ll res = -1;
    for(int i = 0; i < T; ++i) {
        if(res == -1) res = dist[Y[i]];
        else if(dist[Y[i]] != -1) res = min(res, dist[Y[i]]);
    }
    return res;
}

Compilation message

factories.cpp:8:2: warning: #warning checkconstanst as per subtask [-Wcpp]
    8 | #warning checkconstanst as per subtask
      |  ^~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16984 KB Output is correct
2 Correct 2359 ms 21696 KB Output is correct
3 Correct 2289 ms 30908 KB Output is correct
4 Correct 1705 ms 31220 KB Output is correct
5 Correct 1199 ms 30880 KB Output is correct
6 Correct 2490 ms 31520 KB Output is correct
7 Correct 2417 ms 31156 KB Output is correct
8 Correct 2264 ms 31124 KB Output is correct
9 Correct 1205 ms 31184 KB Output is correct
10 Correct 2510 ms 31356 KB Output is correct
11 Correct 2279 ms 30920 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16988 KB Output is correct
2 Runtime error 225 ms 37460 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 25 ms 16984 KB Output is correct
2 Correct 2359 ms 21696 KB Output is correct
3 Correct 2289 ms 30908 KB Output is correct
4 Correct 1705 ms 31220 KB Output is correct
5 Correct 1199 ms 30880 KB Output is correct
6 Correct 2490 ms 31520 KB Output is correct
7 Correct 2417 ms 31156 KB Output is correct
8 Correct 2264 ms 31124 KB Output is correct
9 Correct 1205 ms 31184 KB Output is correct
10 Correct 2510 ms 31356 KB Output is correct
11 Correct 2279 ms 30920 KB Output is correct
12 Correct 18 ms 16988 KB Output is correct
13 Runtime error 225 ms 37460 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -