Submission #39366

#	Time	Username	Problem	Language	Result	Execution time	Memory
39366		wzy	Sightseeing (NOI14_sightseeing)	C++11	25 / 25	2599 ms	166736 KiB

sightseeing

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10