Submission #39364

#	Time	Username	Problem	Language	Result	Execution time	Memory
39364		wzy	Sightseeing (NOI14_sightseeing)	C++11	15 / 25	2493 ms	68236 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define ieps 500500
#define find alice
#define join wonderland
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
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(){
	scanf("%d%d%d" , &n , &m , &q);
	vector<edges> v(m);
	for(int i = 0 ; i < n; i++){
		pai[i] = i , peso[i] = 0;
	}
	for(int i = 0 ; i < m ; i++){
		scanf("%d%d%d" , &v[i].x , &v[i].y, &v[i].z);
		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;
	dfs(0 , 0);
	while(q--){
		int x;
		scanf("%d" , &x);
		printf("%d\n" , custo[x-1]);
	}
}

Compilation message (stderr)

sightseeing.cpp: In function 'int32_t main()':
sightseeing.cpp:44:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d" , &n , &m , &q);
                                ^
sightseeing.cpp:50:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &v[i].x , &v[i].y, &v[i].z);
                                               ^
sightseeing.cpp:65:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
                   ^

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