oj.uz

Submission #1068102

# Submission time Handle Problem Language Result Execution time Memory
1068102 2024-08-21T07:37:47 Z 정민찬(#11128) Paths (RMI21_paths) C++17
68 / 100
 600 ms 12624 KB 
#include <bits/stdc++.h>

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

const ll inf = 2e18;

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';
	}
}

void case2() {
	ll tot = 0;
	for (ll i=1; i<=N; i++) {
		for (auto &[j, c] : adj[i]) {
			if (i < j) tot += c;
		}
	}
	for (ll i=1; i<=N; i++) {
		cout << tot << '\n';
	}
}

ll dp[100010];

void dfs3(ll x, ll p, ll C) {
	ll mx = -1, ch = -1;
	for (auto &[y, c] : adj[x]) {
		if (y == p) continue;
		dfs3(y, x, c);
		if (dp[y] > mx) {
			mx = dp[y];
			ch = y;
		}
	}
	dp[x] = C;
	if (mx != -1) {
		dp[x] += mx;
		dp[ch] = 0;
	}
}

ll solve(ll mid) {
	dfs3(mid, 0, 0);
	sort(dp+1, dp+N+1);
	ll sum = 0;
	for (ll i=0; i<K; i++) {
		sum += dp[N-i];
	}
   	return sum;
}

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;
    }
    ll leaf = 0;
    for (ll i=1; i<=N; i++) {
    	if (adj[i].size() <= 1)
    		leaf ++;
    }
    if (leaf <= K) {
    	case2();
    	return 0;
    }
    for (ll i=1; i<=N; i++) {
    	cout << solve(i) << '\n';
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 28 ms 5044 KB Output is correct
9 Correct 22 ms 2908 KB Output is correct
10 Correct 18 ms 4952 KB Output is correct
11 Correct 25 ms 4956 KB Output is correct
12 Correct 21 ms 5056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 28 ms 5044 KB Output is correct
9 Correct 22 ms 2908 KB Output is correct
10 Correct 18 ms 4952 KB Output is correct
11 Correct 25 ms 4956 KB Output is correct
12 Correct 21 ms 5056 KB Output is correct
13 Correct 123 ms 4956 KB Output is correct
14 Correct 99 ms 5224 KB Output is correct
15 Correct 73 ms 4956 KB Output is correct
16 Correct 125 ms 4952 KB Output is correct
17 Correct 89 ms 4956 KB Output is correct
18 Correct 65 ms 5120 KB Output is correct
19 Correct 140 ms 5124 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11252 KB Output is correct
2 Correct 38 ms 12624 KB Output is correct
3 Correct 44 ms 10832 KB Output is correct
4 Correct 40 ms 10956 KB Output is correct
5 Correct 37 ms 11860 KB Output is correct
6 Correct 34 ms 10956 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 28 ms 5044 KB Output is correct
9 Correct 22 ms 2908 KB Output is correct
10 Correct 18 ms 4952 KB Output is correct
11 Correct 25 ms 4956 KB Output is correct
12 Correct 21 ms 5056 KB Output is correct
13 Correct 123 ms 4956 KB Output is correct
14 Correct 99 ms 5224 KB Output is correct
15 Correct 73 ms 4956 KB Output is correct
16 Correct 125 ms 4952 KB Output is correct
17 Correct 89 ms 4956 KB Output is correct
18 Correct 65 ms 5120 KB Output is correct
19 Correct 140 ms 5124 KB Output is correct
20 Correct 37 ms 11252 KB Output is correct
21 Correct 38 ms 12624 KB Output is correct
22 Correct 44 ms 10832 KB Output is correct
23 Correct 40 ms 10956 KB Output is correct
24 Correct 37 ms 11860 KB Output is correct
25 Correct 34 ms 10956 KB Output is correct
26 Execution timed out 1102 ms 12368 KB Time limit exceeded
27 Halted 0 ms 0 KB -