Submission #391066

#	Time	Username	Problem	Language	Result	Execution time	Memory
391066		wind_reaper	Factories (JOI14_factories)	C++17	15 / 100	8029 ms	56864 KiB

factories

#include <bits/stdc++.h>
#ifndef LOCAL
#include "factories.h"
#endif

using namespace std;

const int MXN = 500000;
const int64_t INF = 1e18;

int N;
vector<pair<int, int64_t>> g[MXN];

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

long long Query(int S, int X[], int T, int Y[]){
	vector<int64_t> dis(N, INF);
	priority_queue< pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>> > pq;

	for(int i = 0; i < S; i++){
		dis[X[i]] = 0;
		pq.emplace(dis[X[i]], X[i]);
	}

	vector<int> vis(N);

	while(!pq.empty()){
		auto [d, u] = pq.top();
		pq.pop();

		if(vis[u])
			continue;
		vis[u] = 1;
		
		for(auto& [v, di] : g[u]){
			if(dis[v] > dis[u] + di){
				dis[v] = dis[u] + di;
				pq.emplace(dis[v], v);
			}
		}
	}

	int64_t ans = INF;
	for(int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i]]);

	return ans;
}

#ifdef LOCAL
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

	int N, Q;
	cin >> N >> Q;
	int A[N-1], B[N-1], D[N-1];

	for(int i = 0; i < N-1; i++){
		cin >> A[i] >> B[i] >> D[i];
	}

	Init(N, A, B, D);

	for(int i = 0; i < Q; i++){
		int S, T;
		cin >> S >> T;
		int X[S], Y[T];
		for(int j = 0; j < S; j++)
			cin >> X[j];
		for(int j = 0; j < T; j++)
			cin >> Y[j];

		cout << Query(S, X, T, Y) << '\n';
	}

	return 0; 
}
#endif

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67