oj.uz

Submission #1014245

# Submission time Handle Problem Language Result Execution time Memory
1014245 2024-07-04T15:12:58 Z adrielcp Factories (JOI14_factories) C++17
15 / 100
 8000 ms 80240 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define ll long long
const ll INF = 1e18;
#define info pair<ll,ll>
vector<vector<info>> adj;
int n;

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

long long Query(int s, int X[], int t, int Y[]) {
  priority_queue<info, vector<info>, greater<info>> pq;
  for (int i = 0; i < s; i++) pq.push({0, X[i]});

  vector<ll> dist(n,INF); // closest dist to any X

  while (!pq.empty()) {
    auto [cost, node] = pq.top();pq.pop();
    if (cost > dist[node]) continue;
    dist[node] = cost;
    for (auto [children, w] : adj[node]) {
      if (cost+w < dist[children]) {
        dist[children] = cost+w;
        pq.push({cost+w, children});
      }
    }
  }

  ll ans = INF;
  for (int i = 0; i < t; i++) {
    // cout << dist[Y[i]] << " t" << endl;
    ans = min(ans, dist[Y[i]]);
  }

  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12888 KB Output is correct
2 Correct 2253 ms 26512 KB Output is correct
3 Correct 2363 ms 30904 KB Output is correct
4 Correct 1744 ms 31184 KB Output is correct
5 Correct 1276 ms 31112 KB Output is correct
6 Correct 2600 ms 31076 KB Output is correct
7 Correct 2231 ms 28852 KB Output is correct
8 Correct 2047 ms 30908 KB Output is correct
9 Correct 1287 ms 29000 KB Output is correct
10 Correct 2543 ms 27044 KB Output is correct
11 Correct 2242 ms 28732 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16884 KB Output is correct
2 Execution timed out 8068 ms 80240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12888 KB Output is correct
2 Correct 2253 ms 26512 KB Output is correct
3 Correct 2363 ms 30904 KB Output is correct
4 Correct 1744 ms 31184 KB Output is correct
5 Correct 1276 ms 31112 KB Output is correct
6 Correct 2600 ms 31076 KB Output is correct
7 Correct 2231 ms 28852 KB Output is correct
8 Correct 2047 ms 30908 KB Output is correct
9 Correct 1287 ms 29000 KB Output is correct
10 Correct 2543 ms 27044 KB Output is correct
11 Correct 2242 ms 28732 KB Output is correct
12 Correct 20 ms 16884 KB Output is correct
13 Execution timed out 8068 ms 80240 KB Time limit exceeded
14 Halted 0 ms 0 KB -