oj.uz

Submission #509724

# Submission time Handle Problem Language Result Execution time Memory
509724 2022-01-14T08:40:59 Z daongocha Paths (RMI21_paths) C++14
56 / 100
 600 ms 13880 KB 
#include <bits/stdc++.h>

#define map dsfakuhwkl34hdfs
#define int long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
 
using namespace std;

const int MAXN = 1e5 + 5;

vector<pair<int, int>> adj[MAXN];
pair<int, int> st[MAXN << 1];
int n, k;
int dep[MAXN];

void build() {
	for (int i = n; i < 2 * n; i++) 
		st[i].second = i - n + 1, st[i].first = dep[i];
	for (int i = n - 1; i >= 1; i--) st[i] = max(st[i << 1], st[i << 1 | 1]);
}

void upd(int i, int val) {
	i += n - 1;
	for (st[i].first = val; i > 1; i >>= 1)
		st[i >> 1] = min(st[i], st[i ^ 1]);
}

pair<int, int> query(int l, int r) {
	l += n - 1;
	r += n;
	pair<int, int> ans = {0, 0};
	for (; l < r; l >>= 1, r >>= 1) {
		if (l & 1) ans = max(ans, st[l++]);
		if (r & 1) ans = max(ans, st[--r]);
	}
	return ans;
}

int par[MAXN];
int num[MAXN];
bool vis[MAXN];

int update(int u) {
	int ans = 0;
	for (; !vis[u]; u = par[u]) {
		ans += num[u];
		vis[u] = 1;
	}
	return ans;
}

void dfs(int u, int pre = 0) {
	par[u] = pre;
	for (auto vw: adj[u]) {
		int v = vw.first, w = vw.second;
		if (v != pre) {
			dep[v] = dep[u] + w;
			num[v] = w;
			dfs(v, u);
		}
	}
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k;

	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	} 

	vis[0] = 1;

	for (int _ = 1; _ <= n; _++) {
		memset(num, 0, sizeof num);
		memset(vis, 0, sizeof vis);
		memset(par, 0, sizeof par);

		vis[0] = 1;

		dfs(_);

		#define pq dsaflkdfssdfdfs
		vector<pair<int, int>> pq;
		for (int i = 1; i <= n; i++) 
			pq.push_back({dep[i], i});

		sort(pq.rbegin(), pq.rend());

		for (int i = 0; i < n; i++) {
			int u = pq[i].second;
			dep[u] = update(u);
		}

		sort(dep + 1, dep + n + 1, greater<int>());

		int res = 0;
		for (int i = 1; i <= k; i++) res += dep[i];

		cout << res << '\n';

		#undef pq
	}

	// for (int i = 1; i <= n; i++) cout << dep[i] << ' '; cout << '\n';
	build();
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 3 ms 4300 KB Output is correct
3 Correct 14 ms 4300 KB Output is correct
4 Correct 13 ms 4356 KB Output is correct
5 Correct 14 ms 4356 KB Output is correct
6 Correct 12 ms 4372 KB Output is correct
7 Correct 13 ms 4364 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 3 ms 4300 KB Output is correct
3 Correct 14 ms 4300 KB Output is correct
4 Correct 13 ms 4356 KB Output is correct
5 Correct 14 ms 4356 KB Output is correct
6 Correct 12 ms 4372 KB Output is correct
7 Correct 13 ms 4364 KB Output is correct
8 Correct 150 ms 4432 KB Output is correct
9 Correct 157 ms 4588 KB Output is correct
10 Correct 150 ms 4428 KB Output is correct
11 Correct 145 ms 4408 KB Output is correct
12 Correct 167 ms 4440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 3 ms 4300 KB Output is correct
3 Correct 14 ms 4300 KB Output is correct
4 Correct 13 ms 4356 KB Output is correct
5 Correct 14 ms 4356 KB Output is correct
6 Correct 12 ms 4372 KB Output is correct
7 Correct 13 ms 4364 KB Output is correct
8 Correct 150 ms 4432 KB Output is correct
9 Correct 157 ms 4588 KB Output is correct
10 Correct 150 ms 4428 KB Output is correct
11 Correct 145 ms 4408 KB Output is correct
12 Correct 167 ms 4440 KB Output is correct
13 Correct 578 ms 4520 KB Output is correct
14 Correct 555 ms 4596 KB Output is correct
15 Correct 511 ms 4548 KB Output is correct
16 Correct 564 ms 4520 KB Output is correct
17 Correct 538 ms 4548 KB Output is correct
18 Correct 340 ms 4504 KB Output is correct
19 Correct 561 ms 4648 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4300 KB Output is correct
2 Correct 3 ms 4300 KB Output is correct
3 Correct 14 ms 4300 KB Output is correct
4 Correct 13 ms 4356 KB Output is correct
5 Correct 14 ms 4356 KB Output is correct
6 Correct 12 ms 4372 KB Output is correct
7 Correct 13 ms 4364 KB Output is correct
8 Correct 150 ms 4432 KB Output is correct
9 Correct 157 ms 4588 KB Output is correct
10 Correct 150 ms 4428 KB Output is correct
11 Correct 145 ms 4408 KB Output is correct
12 Correct 167 ms 4440 KB Output is correct
13 Correct 578 ms 4520 KB Output is correct
14 Correct 555 ms 4596 KB Output is correct
15 Correct 511 ms 4548 KB Output is correct
16 Correct 564 ms 4520 KB Output is correct
17 Correct 538 ms 4548 KB Output is correct
18 Correct 340 ms 4504 KB Output is correct
19 Correct 561 ms 4648 KB Output is correct
20 Execution timed out 1084 ms 13880 KB Time limit exceeded
21 Halted 0 ms 0 KB -