oj.uz

답안 #560822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560822 2022-05-12T03:38:38 Z Garguy22 관광 (NOI14_sightseeing) C++17
25 / 25
 2811 ms 200632 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12088 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 15076 KB Output is correct
2 Correct 39 ms 14772 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1829 ms 123672 KB Output is correct
2 Correct 2811 ms 200632 KB Output is correct