oj.uz

Submission #1085809

# Submission time Handle Problem Language Result Execution time Memory
1085809 2024-09-08T18:13:09 Z Sunbae Sightseeing (NOI14_sightseeing) C++17
25 / 25
 1689 ms 152664 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 5 ms 12120 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12124 KB Output is correct
2 Correct 6 ms 12172 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15076 KB Output is correct
2 Correct 26 ms 14684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1068 ms 96160 KB Output is correct
2 Correct 1689 ms 152664 KB Output is correct