oj.uz

Submission #676153

# Submission time Handle Problem Language Result Execution time Memory
676153 2022-12-29T14:57:52 Z vovamr Paths (RMI21_paths) C++17
36 / 100
 600 ms 19852 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e5 + 10;
const int lg = 17;

int n, k;
ve<pii> gr[N];

int up[N][lg];

ll d[N];
ll mx[N], act[N];

inline void dfs(int v, int p) {
	if (v == p) d[v] = 0;

	up[v][0] = p;
	for (int i = 1; i < lg; ++i) up[v][i] = up[up[v][i - 1]][i - 1];

	mx[v] = v;
	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		d[to] = d[v] + w;
		dfs(to, v);
		if (d[mx[to]] > d[mx[v]]) mx[v] = mx[to];
	}
}
inline void dfs1(int v, int p) {
	if (v != p && sz(gr[v]) == 1) {
		int u = v;
		for (int i = lg - 1; ~i; --i) {
			if (mx[up[u][i]] == v) {
				u = up[u][i];
			}
		}
		act[v] = d[v] - d[up[u][0]];
	}
	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		dfs1(to, v);
	}
}

inline void solve() {
	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		int v, u, c;
		cin >> v >> u >> c, --v, --u;
		gr[v].pb({u, c}), gr[u].pb({v, c});
	}

	for (int i = 0; i < n; ++i) {

		multiset<ll> st;

		dfs(i, i);
		dfs1(i, i);

		for (int v = 0; v < n; ++v) {
			if (sz(gr[v]) == 1 && v != i) {
				st.insert(act[v]);
			}
		}

		ll sum = 0, c = 0;
		while (c < k) {
			sum += *st.rbegin();
			st.erase(--st.end());
			++c;
		}
		cout << sum << '\n';
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 8 ms 2680 KB Output is correct
6 Correct 5 ms 2676 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 8 ms 2680 KB Output is correct
6 Correct 5 ms 2676 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 166 ms 2868 KB Output is correct
9 Correct 142 ms 2860 KB Output is correct
10 Correct 112 ms 2824 KB Output is correct
11 Correct 160 ms 2864 KB Output is correct
12 Correct 122 ms 2844 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 8 ms 2680 KB Output is correct
6 Correct 5 ms 2676 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 166 ms 2868 KB Output is correct
9 Correct 142 ms 2860 KB Output is correct
10 Correct 112 ms 2824 KB Output is correct
11 Correct 160 ms 2864 KB Output is correct
12 Correct 122 ms 2844 KB Output is correct
13 Execution timed out 718 ms 3028 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 19852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 7 ms 2644 KB Output is correct
5 Correct 8 ms 2680 KB Output is correct
6 Correct 5 ms 2676 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 166 ms 2868 KB Output is correct
9 Correct 142 ms 2860 KB Output is correct
10 Correct 112 ms 2824 KB Output is correct
11 Correct 160 ms 2864 KB Output is correct
12 Correct 122 ms 2844 KB Output is correct
13 Execution timed out 718 ms 3028 KB Time limit exceeded
14 Halted 0 ms 0 KB -