oj.uz

Submission #700876

# Submission time Handle Problem Language Result Execution time Memory
700876 2023-02-19T10:04:44 Z Potato3218 Sightseeing (NOI14_sightseeing) C++17
15 / 25
 2561 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define beegspeed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pi pair<int,int>

template<typename T>
void print(T t){
	cout<<t;
	exit(0);
}

vector<pi> adjlist[500007];
signed main(){
	beegspeed
	int n, edges, queries; cin>>n>>edges>>queries;
	for(int i = 0; i < edges; i++){
		int origin, dest, weight; cin>>origin>>dest>>weight;
		adjlist[origin].push_back({dest,weight});
		adjlist[dest].push_back({origin,weight});
	}
	priority_queue<pi> pq;
	pq.push({1000000,1});
	int dist[500007];
	memset(dist, -1, sizeof dist);
	dist[1] = 1000000;
	while(!pq.empty()){
		pi edge = pq.top();
		pq.pop();
		if(edge.first != dist[edge.second]) continue;
		for(auto itr: adjlist[edge.second]){
			if(dist[itr.first] == -1 or dist[itr.first] < min(edge.first, itr.second)){
				dist[itr.first] = min(edge.first, itr.second);
				pq.push({dist[itr.first], itr.first});
			}
		}
	}
	for(int i = 0; i < queries; i++){
		int query; cin>>query;
		cout<<dist[query]<<'\n';
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15972 KB Output is correct
2 Correct 8 ms 15976 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16248 KB Output is correct
2 Correct 10 ms 15988 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 19976 KB Output is correct
2 Correct 30 ms 19100 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2362 ms 251736 KB Output is correct
2 Runtime error 2561 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -