oj.uz

Submission #39365

# Submission time Handle Problem Language Result Execution time Memory
39365 2018-01-13T00:17:21 Z wzy Sightseeing (NOI14_sightseeing) C++11
15 / 25
 2049 ms 114532 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

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;
	dfs(0 , 0);
	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 25480 KB Output is correct
2 Correct 3 ms 25480 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 28540 KB Output is correct
2 Correct 23 ms 28160 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2049 ms 114532 KB Output is correct
2 Runtime error 0 ms 0 KB -1: Interrupted system call