oj.uz

Submission #1036487

# Submission time Handle Problem Language Result Execution time Memory
1036487 2024-07-27T12:41:10 Z andrei_c1 Paths (RMI21_paths) C++17
36 / 100
 600 ms 30768 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();
		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 2 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 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 95 ms 2908 KB Output is correct
9 Correct 128 ms 2908 KB Output is correct
10 Correct 131 ms 2908 KB Output is correct
11 Correct 42 ms 3108 KB Output is correct
12 Correct 84 ms 2908 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 95 ms 2908 KB Output is correct
9 Correct 128 ms 2908 KB Output is correct
10 Correct 131 ms 2908 KB Output is correct
11 Correct 42 ms 3108 KB Output is correct
12 Correct 84 ms 2908 KB Output is correct
13 Execution timed out 609 ms 3400 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 1050 ms 30768 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 6 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 95 ms 2908 KB Output is correct
9 Correct 128 ms 2908 KB Output is correct
10 Correct 131 ms 2908 KB Output is correct
11 Correct 42 ms 3108 KB Output is correct
12 Correct 84 ms 2908 KB Output is correct
13 Execution timed out 609 ms 3400 KB Time limit exceeded
14 Halted 0 ms 0 KB -