oj.uz

Submission #391066

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

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

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12236 KB Output is correct
2 Correct 3535 ms 20548 KB Output is correct
3 Correct 3505 ms 20716 KB Output is correct
4 Correct 2775 ms 20616 KB Output is correct
5 Correct 2068 ms 20652 KB Output is correct
6 Correct 3801 ms 20840 KB Output is correct
7 Correct 3454 ms 20628 KB Output is correct
8 Correct 3384 ms 20676 KB Output is correct
9 Correct 2028 ms 20580 KB Output is correct
10 Correct 3845 ms 20864 KB Output is correct
11 Correct 3495 ms 20484 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12236 KB Output is correct
2 Correct 3535 ms 20548 KB Output is correct
3 Correct 3505 ms 20716 KB Output is correct
4 Correct 2775 ms 20616 KB Output is correct
5 Correct 2068 ms 20652 KB Output is correct
6 Correct 3801 ms 20840 KB Output is correct
7 Correct 3454 ms 20628 KB Output is correct
8 Correct 3384 ms 20676 KB Output is correct
9 Correct 2028 ms 20580 KB Output is correct
10 Correct 3845 ms 20864 KB Output is correct
11 Correct 3495 ms 20484 KB Output is correct
12 Correct 33 ms 12108 KB Output is correct
13 Execution timed out 8029 ms 56864 KB Time limit exceeded
14 Halted 0 ms 0 KB -