oj.uz

Submission #391065

# Submission time Handle Problem Language Result Execution time Memory
391065 2021-04-17T18:00:31 Z wind_reaper Factories (JOI14_factories) C++17
15 / 100
 8000 ms 55716 KB 
#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]);
	}

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

		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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 12492 KB Output is correct
2 Correct 3563 ms 28296 KB Output is correct
3 Correct 3497 ms 28180 KB Output is correct
4 Correct 2762 ms 28416 KB Output is correct
5 Correct 2069 ms 28220 KB Output is correct
6 Correct 3951 ms 28328 KB Output is correct
7 Correct 3529 ms 28144 KB Output is correct
8 Correct 3308 ms 28276 KB Output is correct
9 Correct 2044 ms 28244 KB Output is correct
10 Correct 3911 ms 28716 KB Output is correct
11 Correct 3418 ms 28120 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12200 KB Output is correct
2 Execution timed out 8093 ms 55716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 12492 KB Output is correct
2 Correct 3563 ms 28296 KB Output is correct
3 Correct 3497 ms 28180 KB Output is correct
4 Correct 2762 ms 28416 KB Output is correct
5 Correct 2069 ms 28220 KB Output is correct
6 Correct 3951 ms 28328 KB Output is correct
7 Correct 3529 ms 28144 KB Output is correct
8 Correct 3308 ms 28276 KB Output is correct
9 Correct 2044 ms 28244 KB Output is correct
10 Correct 3911 ms 28716 KB Output is correct
11 Correct 3418 ms 28120 KB Output is correct
12 Correct 33 ms 12200 KB Output is correct
13 Execution timed out 8093 ms 55716 KB Time limit exceeded
14 Halted 0 ms 0 KB -