oj.uz

Submission #1036488

# Submission time Handle Problem Language Result Execution time Memory
1036488 2024-07-27T12:41:50 Z andrei_c1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 28772 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int kN = 1e5;
const int kNil = -1;

int n, k;
vector<pair<int, int>> adj[kN];
vector<int> ord;
int up[kN], val[kN], tin[kN], tout[kN];

void dfs(int u) {
	ord.emplace_back(u);
	tin[u] = ord.size() - 1;
	for(const auto &[to, c]: adj[u]) if(to != up[u]) {
		up[to] = u;
		val[to] = c;
		dfs(to);
	}
	tout[u] = ord.size() - 1;
}

struct node_t {
	ll val;
	int idx;
	node_t() : val(0), idx(0) {}
	node_t(ll val, int idx) : val(val), idx(idx) {}
	node_t operator + (const node_t &oth) const {
		if(val > oth.val) {
			return node_t(val, idx);
		} else {
			return oth;
		}
	};
};

vector<ll> mars;

struct aint {
	int n;
	vector<node_t> tree;
	vector<ll> lazy;
	aint() {}
	aint(int n) : n(n), tree(n << 2 | 1), lazy(n << 2 | 1) {}
	void build(int node, int l, int r) {
		if(l == r) {
			tree[node] = node_t(mars[l], l);
			lazy[node] = 0;
		} else {
			int mid = (l + r) >> 1;
			build(node << 1, l, mid);
			build(node << 1 | 1, mid + 1, r);
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void build() {
		build(1, 0, n - 1);
	}
	void push(int node) {
		if(lazy[node]) {
			for(const auto &it: {node << 1, node << 1 | 1}) {
				tree[it].val += lazy[node];
				lazy[it] += lazy[node];
			}
			lazy[node] = 0;
		}
	}
	void update(int a, int b, int val, int node, int l, int r) {
		if(a <= l && r <= b) {
			tree[node].val += val;
			lazy[node] += val;
		} else {
			push(node);
			int mid = (l + r) >> 1;
			if(a <= mid) {
				update(a, b, val, node << 1, l, mid);
			}
			if(b > mid) {
				update(a, b, val, node << 1 | 1, mid + 1, r);
			}
			tree[node] = tree[node << 1] + tree[node << 1 | 1];
		}
	}
	void update(int a, int b, int val) {
		update(a, b, val, 1, 0, n - 1);
	}
	inline node_t all() {
		return tree[1];
	}
} ds;

ll solve(int root) {
	ll res = 0;
	up[root] = kNil;
	val[root] = 0;
	dfs(root);
	mars = vector<ll>(n + 1);
	for(int i = 0; i < n; i++) {
		mars[tin[i]] += val[i];
		mars[tout[i] + 1] -= val[i];
	}
	for(int i = 1; i < n; i++) {
		mars[i] += mars[i - 1];
	}
	ds = aint(n);
	ds.build();
	vector<bool> vis(n);
	for(int i = 0; i < k; i++) {
		auto [sum, idx] = ds.all();
		if(sum == 0) {
			break;
		}
		res += sum;
		int u = ord[idx];
		while(u != kNil && !vis[u]) {
			vis[u] = true;
			ds.update(tin[u], tout[u], -val[u]);
			u = up[u];
		}
	}
	ord.clear();
	return res;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 1; i < n; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		u--; v--;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}
	for(int i = 0; i < n; i++) {
		cout << solve(i) << '\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2648 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 2 ms 2880 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 5 ms 2652 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2648 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 2 ms 2880 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 5 ms 2652 KB Output is correct
8 Correct 85 ms 2904 KB Output is correct
9 Correct 126 ms 2908 KB Output is correct
10 Correct 128 ms 2908 KB Output is correct
11 Correct 41 ms 2904 KB Output is correct
12 Correct 82 ms 2908 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2648 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 2 ms 2880 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 5 ms 2652 KB Output is correct
8 Correct 85 ms 2904 KB Output is correct
9 Correct 126 ms 2908 KB Output is correct
10 Correct 128 ms 2908 KB Output is correct
11 Correct 41 ms 2904 KB Output is correct
12 Correct 82 ms 2908 KB Output is correct
13 Correct 596 ms 3344 KB Output is correct
14 Correct 543 ms 3464 KB Output is correct
15 Correct 496 ms 3420 KB Output is correct
16 Correct 370 ms 3392 KB Output is correct
17 Execution timed out 651 ms 3376 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2648 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 2 ms 2880 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 5 ms 2652 KB Output is correct
8 Correct 85 ms 2904 KB Output is correct
9 Correct 126 ms 2908 KB Output is correct
10 Correct 128 ms 2908 KB Output is correct
11 Correct 41 ms 2904 KB Output is correct
12 Correct 82 ms 2908 KB Output is correct
13 Correct 596 ms 3344 KB Output is correct
14 Correct 543 ms 3464 KB Output is correct
15 Correct 496 ms 3420 KB Output is correct
16 Correct 370 ms 3392 KB Output is correct
17 Execution timed out 651 ms 3376 KB Time limit exceeded
18 Halted 0 ms 0 KB -