Submission #791290

#	Time	Username	Problem	Language	Result	Execution time	Memory
791290		bane	Factories (JOI14_factories)	C++17	0 / 100	921 ms	8860 KiB

factories

#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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67