Submission #1085809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085809		Sunbae	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1689 ms	152664 KiB

sightseeing

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
const int N = 5e5 + 5, M = 5e6 + 5;
int sz[N], p[N], dp[N];
tuple<int,int,int> e[M];
vector<pair<int,int>> g[N];

void dfs(int u, int p){
	for(pair<int,int> it: g[u]){
		int w = it.first, v = it.second;
		if(v != p) dp[v] = min(w, dp[u]), dfs(v, u);
	}
}

int fp(int u){ return u == p[u] ? u : p[u] = fp(p[u]);}

signed main(){
	int n, m, q; scanf("%d %d %d", &n, &m, &q); 
	for(int i = 0; i<n; ++i) p[i] = i, sz[i] = 1;
	for(int i = 0, u, v, w; i<m; ++i){
		scanf("%d %d %d", &u, &v, &w); --u; --v;
		e[i] = make_tuple(-w, u, v);
	}
	sort(e, e+m);
	for(int i = 0; i<m; ++i){
		int w, u, v; tie(w, u, v) = e[i]; w = -w;
		if(fp(u) != fp(v)){
			g[u].emplace_back(w, v); 
			g[v].emplace_back(w, u);
			u = fp(u); v = fp(v);
			if(sz[u] < sz[v]) swap(u, v);
			sz[u] += sz[v]; sz[v] = 0;
			p[v] = u;
		}
	}
	dp[0] = 1e9;
	dfs(0, 0);
	for(int u; q--; ) scanf("%d", &u), printf("%d\n", dp[--u]);
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  int n, m, q; scanf("%d %d %d", &n, &m, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d %d %d", &u, &v, &w); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  for(int u; q--; ) scanf("%d", &u), printf("%d\n", dp[--u]);
      |                    ~~~~~^~~~~~~~~~

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