oj.uz

Submission #322279

# Submission time Handle Problem Language Result Execution time Memory
322279 2020-11-14T11:19:47 Z Sparky_09 Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 100284 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int INF = INT_MAX; 
vector<int> dist, U, sz;

int getParents(int a){
	if(U[a] == a) return a;
	else return U[a] = getParents(U[a]);
}
 
void Union(int a, int b){
	a = getParents(a);
	b = getParents(b);
	
	if(sz[a] < sz[b]){
		sz[a] += sz[b];
		U[a] = U[b];
	}else{
		sz[b] += sz[a];
		U[b] = U[a];
	}
}
 
vector<vector<pair<int, int>>> Graph;
 
vector<bool> visited;
 
void dfs(int node, int cost){
	dist[node] = cost;
	visited[node] = true;
	for(pair<int, int> p : Graph[node]){
		if(visited[p.first]) continue;
		dfs(p.first, min(cost, p.second));
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	
	Graph.resize(n+1);
	
	vector<tuple<int, int, int>> edges(m);
	
	for(int i = 0; i < m; i++){		
		int a, b, c;
		cin >> a >> b >> c;
		edges[i] = make_tuple(c,a,b);
	}
	
	sz.assign(n+1,1);
	dist.resize(n+1);
	U.resize(n+1);
	
	for(int i = 1; i <= n; i++){
		U[i] = i;
	}
	
	sort(edges.rbegin(), edges.rend());
	
	for(int i = 0; i < m; i++){
		int a = get<1>(edges[i]);
		int b = get<2>(edges[i]);
		int c = get<0>(edges[i]);
		
		if(getParents(a) == getParents(b)){
			continue;
		}
		Union(a,b);
		
		Graph[a].push_back(make_pair(b,c));
		Graph[b].push_back(make_pair(a,c));
	}
	visited.assign(n+1, false);
	dfs(1,INF);
	
	for(int i = 0; i < q; i++){
		int a;
		cin >> a;
		cout << dist[a] << '\n';
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3564 KB Output is correct
2 Correct 41 ms 3308 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2455 ms 63508 KB Output is correct
2 Execution timed out 3558 ms 100284 KB Time limit exceeded