oj.uz

Submission #1067921

# Submission time Handle Problem Language Result Execution time Memory
1067921 2024-08-21T05:35:52 Z 정민찬(#11128) Paths (RMI21_paths) C++17
12 / 100
 47 ms 14164 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

vector<pll> adj[100010];

ll down[100010];
ll up[100010];
ll N, K;

void dfs1(ll x, ll p) {
	down[x] = 0;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		dfs1(y, x);
		down[x] = max(down[x], down[y] + c);
	}
}

void dfs2(ll x, ll p) {
	ll mx1 = 0, mx2 = 0;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		if (mx1 < down[y] + c) {
			mx2 = mx1; mx1 = down[y] + c;
		}
		else if (mx2 < down[y] + c) {
			mx2 = down[y] + c;
		}
	}
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		up[y] = up[x] + c;
		if (mx1 == down[y] + c) up[y] = max(up[y], mx2 + c);
		else up[y] = max(up[y], mx1 + c);
		dfs2(y, x);
	}
}

void case1() {
	dfs1(1, 0);
	dfs2(1, 0);
	for (ll i=1; i<=N; i++) {
		cout << max(up[i], down[i]) << '\n';
	}
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    
    cin >> N >> K;
    for (ll i=0; i<N-1; i++) {
    	ll u, v, c;
    	cin >> u >> v >> c;
    	adj[u].push_back({v, c});
    	adj[v].push_back({u, c});
    }
    if (K == 1) {
    	case1();
    	return 0;
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4188 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 4188 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 4188 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 4188 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 41 ms 10580 KB Output is correct
2 Correct 40 ms 14164 KB Output is correct
3 Correct 36 ms 12368 KB Output is correct
4 Correct 40 ms 12492 KB Output is correct
5 Correct 47 ms 13380 KB Output is correct
6 Correct 44 ms 12360 KB Output is correct

Subtask #6
0 / 32.0

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