oj.uz

Submission #1063337

# Submission time Handle Problem Language Result Execution time Memory
1063337 2024-08-17T16:59:31 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 72624 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

void dijkstra();

ll inf = LONG_LONG_MAX;
int n;
vector<vector<pair<int, ll>>> adj(500005);
vector<bool> vis(500005, 0);
vector<ll> dis(500005, inf);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

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

long long Query(int S, int X[], int T, int Y[])
{
  for (int i = 0; i < n; i++)
  {
    vis[i] = 0;
    dis[i] = inf;
  }
  for (int i = 0; i < T; i++)
  {
    dis[Y[i]] = 0;
    pq.push({0, Y[i]});
  }

  dijkstra();

  ll ans = inf;
  for (int i = 0; i < S; i++)
  {
    ans = min(ans, dis[X[i]]);
  }

  return ans;
}

void dijkstra()
{
  while (!pq.empty())
  {
    int a = pq.top().second;
    pq.pop();

    if (vis[a])
      continue;
    vis[a] = 1;

    for (auto [b, w] : adj[a])
    {
      if (dis[b] > dis[a] + w)
      {
        dis[b] = dis[a] + w;
        pq.push({dis[b], b});
      }
    }
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16472 KB Output is correct
2 Correct 2307 ms 33872 KB Output is correct
3 Correct 2300 ms 33872 KB Output is correct
4 Correct 2186 ms 33876 KB Output is correct
5 Correct 1389 ms 33872 KB Output is correct
6 Correct 2450 ms 34132 KB Output is correct
7 Correct 2309 ms 33944 KB Output is correct
8 Correct 1709 ms 34128 KB Output is correct
9 Correct 1361 ms 33876 KB Output is correct
10 Correct 2493 ms 34076 KB Output is correct
11 Correct 2227 ms 33820 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16216 KB Output is correct
2 Execution timed out 8058 ms 72624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16472 KB Output is correct
2 Correct 2307 ms 33872 KB Output is correct
3 Correct 2300 ms 33872 KB Output is correct
4 Correct 2186 ms 33876 KB Output is correct
5 Correct 1389 ms 33872 KB Output is correct
6 Correct 2450 ms 34132 KB Output is correct
7 Correct 2309 ms 33944 KB Output is correct
8 Correct 1709 ms 34128 KB Output is correct
9 Correct 1361 ms 33876 KB Output is correct
10 Correct 2493 ms 34076 KB Output is correct
11 Correct 2227 ms 33820 KB Output is correct
12 Correct 23 ms 16216 KB Output is correct
13 Execution timed out 8058 ms 72624 KB Time limit exceeded
14 Halted 0 ms 0 KB -