oj.uz

Submission #512545

# Submission time Handle Problem Language Result Execution time Memory
512545 2022-01-16T12:52:54 Z hollwo_pelw Paths (RMI21_paths) C++17
100 / 100
 248 ms 15984 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> in, out;

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

	inline void add(int64_t v) {
		if (*in.begin() >= v && in.size() == k) {
			out.insert(v);
		} else {
			in.insert(v);
			val += v;

			if (in.size() > k) {
				v = *in.begin();
				out.insert(v);
				
				in.erase(in.begin());
				val -= v;
			}
		}
	}

	inline void del(int64_t v) {
		if (out.find(v) != out.end()) {
			out.erase(out.find(v));
		} else {
			in.erase(in.find(v));
			val -= v;

			if (out.size() > 0) {
				v = *out.rbegin();
				out.erase(out.find(v));

				in.insert(v);
				val += v;
			}
		}
	}

	inline int64_t get_val() {
		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 member function 'void maxk::add(int64_t)':
Main.cpp:58:37: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |   if (*in.begin() >= v && in.size() == k) {
      |                           ~~~~~~~~~~^~~~
Main.cpp:64:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |    if (in.size() > k) {
      |        ~~~~~~~~~~^~~
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 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 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 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 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 2664 KB Output is correct
9 Correct 3 ms 2716 KB Output is correct
10 Correct 3 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 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 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 2664 KB Output is correct
9 Correct 3 ms 2716 KB Output is correct
10 Correct 3 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 6 ms 2804 KB Output is correct
14 Correct 6 ms 2892 KB Output is correct
15 Correct 6 ms 2812 KB Output is correct
16 Correct 4 ms 2892 KB Output is correct
17 Correct 4 ms 2764 KB Output is correct
18 Correct 3 ms 2808 KB Output is correct
19 Correct 4 ms 2892 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 12340 KB Output is correct
2 Correct 222 ms 15328 KB Output is correct
3 Correct 141 ms 10604 KB Output is correct
4 Correct 248 ms 13252 KB Output is correct
5 Correct 187 ms 15116 KB Output is correct
6 Correct 188 ms 12608 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 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 2664 KB Output is correct
9 Correct 3 ms 2716 KB Output is correct
10 Correct 3 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 6 ms 2804 KB Output is correct
14 Correct 6 ms 2892 KB Output is correct
15 Correct 6 ms 2812 KB Output is correct
16 Correct 4 ms 2892 KB Output is correct
17 Correct 4 ms 2764 KB Output is correct
18 Correct 3 ms 2808 KB Output is correct
19 Correct 4 ms 2892 KB Output is correct
20 Correct 192 ms 12340 KB Output is correct
21 Correct 222 ms 15328 KB Output is correct
22 Correct 141 ms 10604 KB Output is correct
23 Correct 248 ms 13252 KB Output is correct
24 Correct 187 ms 15116 KB Output is correct
25 Correct 188 ms 12608 KB Output is correct
26 Correct 229 ms 13048 KB Output is correct
27 Correct 223 ms 15084 KB Output is correct
28 Correct 239 ms 15984 KB Output is correct
29 Correct 170 ms 12104 KB Output is correct
30 Correct 226 ms 12764 KB Output is correct
31 Correct 224 ms 12856 KB Output is correct
32 Correct 248 ms 15172 KB Output is correct
33 Correct 239 ms 12916 KB Output is correct
34 Correct 129 ms 9996 KB Output is correct
35 Correct 227 ms 12728 KB Output is correct
36 Correct 212 ms 14644 KB Output is correct