oj.uz

Submission #791289

# Submission time Handle Problem Language Result Execution time Memory
791289 2023-07-23T23:16:42 Z bane Factories (JOI14_factories) C++17
0 / 100
 8000 ms 104124 KB 
#include<bits/stdc++.h>
using namespace std;
#include "factories.h"

vector<vector<pair<int,int>>>G;

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

}

long long Query(int S, int X[], int T, int Y[]) {
  priority_queue<pair<long long, int>>q;
  map<long long, long long>mapa;
  map<int,int>flag;
  for (int i = 0; i < T; i++)flag[Y[i]] = 1;
  for (int i = 0; i < S; i++){
    q.push({0,X[i]});
    mapa[X[i]] = 0;
  }

  while(!q.empty()){
    auto [dist,node] = q.top();
    q.pop();
    dist = -dist;
    if (dist != mapa[node])continue;
    if (flag[node]){
      return dist;
    }
    for(auto edge : G[node]){
      if (!mapa.count(edge.first) || mapa[edge.first] > dist + edge.second){
        mapa[edge.first] = dist + edge.second;
        q.push({-dist-edge.second, edge.first});
      }
    }
  }
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 856 KB Output is correct
2 Correct 5740 ms 18680 KB Output is correct
3 Correct 1071 ms 18188 KB Output is correct
4 Correct 2153 ms 18760 KB Output is correct
5 Correct 4665 ms 18696 KB Output is correct
6 Execution timed out 8053 ms 18800 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 508 KB Output is correct
2 Execution timed out 8063 ms 104124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 856 KB Output is correct
2 Correct 5740 ms 18680 KB Output is correct
3 Correct 1071 ms 18188 KB Output is correct
4 Correct 2153 ms 18760 KB Output is correct
5 Correct 4665 ms 18696 KB Output is correct
6 Execution timed out 8053 ms 18800 KB Time limit exceeded
7 Halted 0 ms 0 KB -