oj.uz

Submission #39366

# Submission time Handle Problem Language Result Execution time Memory
39366 2018-01-13T00:23:16 Z wzy Sightseeing (NOI14_sightseeing) C++11
25 / 25
 2599 ms 166736 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define int long long
#define ieps 500500
#define find alice
#define join wonderland
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
bool vis[ieps];
inline int read_int() {
   register char c=0;
   int a=0;
   while (c<33) c=getchar();
   while (c>33) {
       a=a*10+c-'0', c=getchar();
   }
   return a;
}

int pai[ieps] , n , m , q ,  peso[ieps] , custo[ieps];

int find(int x){
	return pai[x] == x ? x : pai[x] = find(pai[x]);
}

void join(int u , int v){
	u = find(u) , v = find(v);
	if(peso[u] > peso[v]) swap(u, v);
	pai[u] = v , peso[v] += peso[u];
}


struct edges{
	int x,  y , z;
};
vector<pii> adj[ieps];

bool cmp(edges a , edges b){
	return a.z > b.z;
}

void dfs(int x , int y){
	for(auto t : adj[x]){
		if(t.F == y) continue;
		custo[t.F] = min(t.S , custo[x]);
		dfs(t.F, x);
	}
}


int32_t main(){
	n = read_int() , m = read_int() , q = read_int();
	vector<edges> v(m);
	for(int i = 0 ; i < n; i++){
		pai[i] = i , peso[i] = 0;
	}
	for(int i = 0 ; i < m ; i++){
		v[i].x = read_int() , v[i].y = read_int() , v[i].z = read_int();
		v[i].x -- , v[i].y--;
	}
	sort(v.begin() , v.end() , cmp);
	for(int i = 0 ; i < m; i++){
		if(find(v[i].x) != find(v[i].y)){
			join(v[i].x , v[i].y);
			adj[v[i].x].pb(pii(v[i].y , v[i].z));
			adj[v[i].y].pb(pii(v[i].x , v[i].z));
		}
	}
	for(int i = 0 ; i < ieps; i++) custo[i] = eps;
	queue<int> w;
	w.push(0);
	while(!w.empty()){
		int u = w.front();
		w.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(auto t :adj[u]){
			if(vis[t.F]) continue;
			custo[t.F] = min(t.S , custo[u]);
			w.push(t.F);
		}
	}
	while(q--){
		int x;
		x = read_int();
		printf("%lld\n" , custo[x-1]);
	}
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 29032 KB Output is correct
2 Correct 29 ms 28652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2016 ms 115156 KB Output is correct
2 Correct 2599 ms 166736 KB Output is correct