Submission #560822

#	Time	Username	Problem	Language	Result	Execution time	Memory
560822		Garguy22	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	2811 ms	200632 KiB

sightseeing

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
#define mp make_pair

const int MAXV = 5e5 + 7;
const int INF = 1e9 + 7;

vector<pii> adj[MAXV];
int parent[MAXV], ans[MAXV];

int find(int u){
	if(parent[u] == u) 
		return u;
	return parent[u] = find(parent[u]); 
}

void merge(int x, int y){
	x = find(x);
	y = find(y);
	parent[x] = y;
}

void dfs(int x, int y){
	for(auto temp : adj[x]){
		int z = temp.first, w = temp.second;
		if(y != z){
			ans[z] = min(ans[x], w);
			dfs(z, x);
		}
	}
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int v, e, q;
	cin >> v >> e >> q;
	pair<int, pii> edges[e];
	for(int i = 0; i < e; i++){
		int x, y, z;
		cin >> x >> y >> z;
		edges[i].first = z;
		edges[i].second.first = x;
		edges[i].second.second = y;
	}
	sort(edges, edges + e);
	reverse(edges, edges + e);
	for(int i = 1; i <= v; i++)
		parent[i] = i;
	for(auto u : edges){
		int wt = u.first, x = u.second.first, y = u.second.second;
		int a = find(x);
		int b = find(y);
		if(a != b){
			adj[x].push_back(mp(y, wt));
			adj[y].push_back(mp(x, wt));
			merge(x, y);
		}
	}
	ans[1] = INF;
	dfs(1, -1);
	for(int i = 0; i < q; i++){
		int u;
		cin >> u;
		cout << ans[u] << endl;
	}

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10