oj.uz

Submission #39364

# Submission time Handle Problem Language Result Execution time Memory
39364 2018-01-12T21:09:50 Z wzy Sightseeing (NOI14_sightseeing) C++11
15 / 25
 2493 ms 68236 KB 
#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

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.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 21544 KB Output is correct
2 Correct 33 ms 21288 KB Output is correct

Subtask #4
0 / 10.0

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