oj.uz

Submission #871309

# Submission time Handle Problem Language Result Execution time Memory
871309 2023-11-10T14:29:24 Z TAhmed33 Paths (RMI21_paths) C++
12 / 100
 61 ms 11624 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
int mx = 0, en = 0;
void dfs (int pos, int par, int dist) {
	if (dist >= mx) {
		mx = dist;
		en = pos;
	}
	for (auto j : adj[pos]) if (j.first != par) dfs(j.first, pos, dist + j.second);
}
int dist1[MAXN][2];
void dfs2 (int pos, int par, int dist, int c) {
	dist1[pos][c] = dist;
	for (auto j : adj[pos]) if (j.first != par) dfs2(j.first, pos, dist + j.second, c);
}
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	dfs(1, -1, 0);
	int f1 = en;
	en = 0; mx = 0;
	dfs(f1, -1, 0);
	int f2 = en;
	dfs2(f1, -1, 0, 0);
	dfs2(f2, -1, 0, 1);
	for (int i = 1; i <= n; i++) cout << max(dist1[i][0], dist1[i][1]) << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4184 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 4184 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 4184 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 4184 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 51 ms 10580 KB Output is correct
2 Correct 48 ms 11624 KB Output is correct
3 Correct 50 ms 10496 KB Output is correct
4 Correct 44 ms 10456 KB Output is correct
5 Correct 61 ms 11344 KB Output is correct
6 Correct 43 ms 10188 KB Output is correct

Subtask #6
0 / 32.0

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