Submission #509724

#	Time	Username	Problem	Language	Result	Execution time	Memory
509724		daongocha	Paths (RMI21_paths)	C++14	56 / 100	1084 ms	13880 KiB

Main

#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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32