Submission #871309

#	Time	Username	Problem	Language	Result	Execution time	Memory
871309		TAhmed33	Paths (RMI21_paths)	C++98	12 / 100	61 ms	11624 KiB

Main

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32