oj.uz

Submission #511303

# Submission time Handle Problem Language Result Execution time Memory
511303 2022-01-15T14:07:55 Z hollwo_pelw Paths (RMI21_paths) C++17
68 / 100
 600 ms 15360 KB 
/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

const int N = 1e5 + 5;

struct maxk {
	int k; int64_t val;
	multiset<int64_t> st;

	inline void __init__(int _k) { k = _k; }

	inline void add(int64_t v) {
		st.insert(v);
	}

	inline void del(int64_t v) {
		st.erase(st.find(v));
	}

	inline int64_t get_val() {
		val = 0;
		auto it = st.end();
		for (int q = k; q -- && it != st.begin(); )
			val += *(-- it);
		return val;
	}
} calc;

int n, k;
vector<pair<int, int>> adj[N];
int64_t up[N], dw[N], res[N];

void dfs_dw(int u, int p) {
	for (auto [v, w] : adj[u]) if (v != p) {
		dfs_dw(v, u);
		dw[u] = max(dw[u], dw[v] + w);
	}
}

void dfs_up(int u, int p) {
	int64_t vf = 0, vs = 0;
	int f = 0, s = 0;
	for (auto [v, w] : adj[u])
		if (v != p) {
			int64_t vv = dw[v] + w;
			if (vf < vv) swap(f, v), swap(vf, vv);
			if (vs < vv) swap(s, v), swap(vs, vv);
		}
	for (auto [v, w] : adj[u])
		if (v != p && v != f) {
			calc.add(dw[v] + w);
	}

	for (auto [v, w] : adj[u])
		if (v != p) {
			up[v] = max(up[u], v == f ? vs : vf) + w;
			dfs_up(v, u);
		}
}

void reroot(int u, int p) {
	// cout << "solve " << u << '\n';
	res[u] = calc.get_val();
	for (auto [v, w] : adj[u])
		if (v != p) {
			calc.add(dw[v]), calc.del(dw[v] + w);
			calc.add(up[v]), calc.del(up[v] - w);
			reroot(v, u);
			calc.add(dw[v] + w), calc.del(dw[v]);
			calc.add(up[v] - w), calc.del(up[v]);
		}
}

void Hollwo_Pelw() {
	cin >> n >> k;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	calc.__init__(k);
	dfs_dw(1, 0);
	dfs_up(1, 0);

	calc.add(dw[1]);
	if (adj[1].size() == 1)
		calc.add(up[1]);

	reroot(1, 0);

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

Compilation message

Main.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
Main.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2708 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 3 ms 2672 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2708 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 3 ms 2672 KB Output is correct
13 Correct 13 ms 2852 KB Output is correct
14 Correct 5 ms 2892 KB Output is correct
15 Correct 5 ms 2764 KB Output is correct
16 Correct 11 ms 2880 KB Output is correct
17 Correct 7 ms 2840 KB Output is correct
18 Correct 5 ms 2764 KB Output is correct
19 Correct 16 ms 2852 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 12368 KB Output is correct
2 Correct 224 ms 15360 KB Output is correct
3 Correct 127 ms 10540 KB Output is correct
4 Correct 231 ms 13272 KB Output is correct
5 Correct 211 ms 15144 KB Output is correct
6 Correct 179 ms 12512 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2708 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 3 ms 2672 KB Output is correct
13 Correct 13 ms 2852 KB Output is correct
14 Correct 5 ms 2892 KB Output is correct
15 Correct 5 ms 2764 KB Output is correct
16 Correct 11 ms 2880 KB Output is correct
17 Correct 7 ms 2840 KB Output is correct
18 Correct 5 ms 2764 KB Output is correct
19 Correct 16 ms 2852 KB Output is correct
20 Correct 210 ms 12368 KB Output is correct
21 Correct 224 ms 15360 KB Output is correct
22 Correct 127 ms 10540 KB Output is correct
23 Correct 231 ms 13272 KB Output is correct
24 Correct 211 ms 15144 KB Output is correct
25 Correct 179 ms 12512 KB Output is correct
26 Execution timed out 1062 ms 11576 KB Time limit exceeded
27 Halted 0 ms 0 KB -