oj.uz

Submission #791290

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

vector<vector<pair<int,int>>>G;
vector<long long>mapa;
int n;
int flag[(int)5e5+1];
void Init(int N, int A[], int B[], int D[]) {
  G.resize(N+1);
  mapa.resize(N+1);
  mapa.assign(N+1,(long long)1e18);
  n = N;
  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;
  
  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]){
      for (int i = 0; i < T; i++)flag[Y[i]] = 0;
      for (int i = 1; i<= n; i++)mapa[i] = (long long)1e18;
      return dist;
    }
    for(auto edge : G[node]){
      if (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 8 ms 724 KB Output is correct
2 Incorrect 921 ms 8860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 724 KB Output is correct
2 Incorrect 921 ms 8860 KB Output isn't correct
3 Halted 0 ms 0 KB -