oj.uz

Submission #1067932

# Submission time Handle Problem Language Result Execution time Memory
1067932 2024-08-21T05:45:03 Z 김은성(#11126) Paths (RMI21_paths) C++17
12 / 100
 54 ms 11348 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 9;
typedef long long ll;
vector<pair<int, ll> > graph[MAXN];
ll dist[MAXN], ans[MAXN];
void dfs(int v, ll d){
	if(dist[v] != -1)
		return;
	dist[v] = d;
	for(auto [u, c]: graph[v]){
		dfs(u, d + c);
	}
}
int main(){
	int n, k, i, j, a, b;
	ll c;
	scanf("%d %d", &n, &k);
	for(i=1; i<n; i++){
		scanf("%d %d %lld", &a, &b, &c);
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
	memset(dist, -1, sizeof(dist));
	dfs(1, 0);
	int x0, y0;
	ll mx = -1;
	for(i=1; i<=n; i++){
		if(dist[i] > mx){
			mx = dist[i];
			x0 = i;
		}
	}
	memset(dist, -1, sizeof(dist));
	dfs(x0, 0);
	mx = -1;
	for(i=1; i<=n; i++){
		if(dist[i] > mx){
			mx = dist[i];
			y0 = i;
		}
		ans[i] = dist[i];
	}
	memset(dist, -1, sizeof(dist));
	dfs(y0, 0);
	for(i=1; i<=n; i++){
		ans[i] = max(ans[i], dist[i]);
	}
	for(i=1; i<=n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:16:15: warning: unused variable 'j' [-Wunused-variable]
   16 |  int n, k, i, j, a, b;
      |               ^
Main.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d %d %lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:5: warning: 'y0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |  dfs(y0, 0);
      |  ~~~^~~~~~~
Main.cpp:35:5: warning: 'x0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |  dfs(x0, 0);
      |  ~~~^~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10576 KB Output is correct
2 Correct 54 ms 11348 KB Output is correct
3 Correct 43 ms 10324 KB Output is correct
4 Correct 46 ms 10448 KB Output is correct
5 Correct 45 ms 11088 KB Output is correct
6 Correct 40 ms 10180 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -