oj.uz

Submission #509759

# Submission time Handle Problem Language Result Execution time Memory
509759 2022-01-14T09:26:39 Z minhcool Paths (RMI21_paths) C++17
100 / 100
 575 ms 38256 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ordered_set tree<ii, null_type, greater<ii>, rb_tree_tag, tree_order_statistics_node_update>
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, k;
vector<ii> Adj[N];
 
int cnt;
int edg[N];
int l[N], r[N], p[N], d[N], rev[N];// rev: reverse of euler tour
 
int mx[N << 2], pos[N << 2];
 
int laz[N << 2];
 
int par[N];
bool vis[N];
 
void build(int id, int l, int r){
	if(l == r){
		mx[id] = d[rev[l]];
		pos[id] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
	pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
}
 
void er(int id, int l, int r, int posi){
	if(l == r){
		mx[id] = -oo;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= posi) er(id << 1, l, mid, posi);
	else er(id << 1 | 1, mid + 1, r, posi);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
	pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
	mx[id] -= laz[id];
}
 
void upd(int id, int l, int r, int L, int R, int val){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		laz[id] += val;
		mx[id] -= val;
		return;
	}
	int mid = (l + r) >> 1;
	upd(id << 1, l, mid, L, R, val);
	upd(id << 1 | 1, mid + 1, r, L, R, val);
	mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
	pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
	mx[id] -= laz[id];
}
 
void dfs(int u, int pa){
	cnt++;
	l[u] = p[u] = cnt;
	for(auto it : Adj[u]){
		int v = it.fi, w = it.se;
		if(v == pa) continue;
		par[v] = u;
		d[v] = d[u] + w;
		edg[v] = w;
		dfs(v, u);
	}
	r[u] = cnt;
}

int vertex[N];

int IT2[N << 2];

ordered_set os;

void build2(int id, int l, int r){
	if(l == r){
		IT2[id] = vertex[l];
		mx[id] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build2(id << 1, l, mid);
	build2(id << 1 | 1, mid + 1, r);
	IT2[id] = max(IT2[id << 1], IT2[id << 1 | 1]);
	mx[id] = (IT2[id << 1] == IT2[id] ? mx[id << 1] : mx[id << 1 | 1]);
}

void upd(int id, int l, int r, int pos, int val){
	if(l == r){
		IT2[id] += val;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos) upd(id << 1, l, mid, pos, val);
	else upd(id << 1 | 1, mid + 1, r, pos, val);
	IT2[id] = max(IT2[id << 1], IT2[id << 1 | 1]);
	mx[id] = (IT2[id << 1] == IT2[id] ? mx[id << 1] : mx[id << 1 | 1]);
}

ii get(int id, int l, int r, int L, int R){
	if(l > R || r < L || l > r) return {-oo, -oo};
	if(l >= L && r <= R) return {IT2[id], mx[id]};
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}

int answer[N];
int contain[N];

void dfs_ans(int u, int p){
	for(auto it : Adj[u]){
		int v = it.fi, w = it.se;
		if(v == p) continue;
		ii temp1 = get(1, 1, n, l[v], r[v]);
		ii temp2 = max(get(1, 1, n, 1, l[v] - 1), get(1, 1, n, r[v] + 1, n));
		answer[v] = answer[u];
		//cout << v << " " << contain[v] << " " << vertex[contain[v]] << "\n";
		if(w > 0){
		os.erase({vertex[contain[v]], contain[v]});
		os.insert({vertex[contain[v]] - w, contain[v]});
		assert(os.size() == n);
		//cout << (*os.find_by_order(k - 1)).fi << "\n";
		answer[v] -= max(0LL, vertex[contain[v]] - max(vertex[contain[v]] - w, (*os.find_by_order(k - 1)).fi));
		vertex[contain[v]] -= w;
		upd(1, 1, n, contain[v], -w);
		int temp = (*os.find_by_order(k - 1)).fi;
		os.erase({vertex[temp2.se], temp2.se});
		os.insert({vertex[temp2.se] + w, temp2.se});
		assert(os.size() == n);
		answer[v] += max(0LL, (vertex[temp2.se] + w) - max(vertex[temp2.se], temp));
		vertex[temp2.se] += w;
		}
		upd(1, 1, n, temp2.se, w);
		dfs_ans(v, u);
		if(w > 0){
		vertex[contain[v]] += w;
		os.insert({vertex[contain[v]], contain[v]});
		os.erase({vertex[contain[v]] - w, contain[v]});
		assert(os.size() == n);
		vertex[temp2.se] -= w;
		os.insert({vertex[temp2.se], temp2.se});
		os.erase({vertex[temp2.se] + w, temp2.se});
		assert(os.size() == n);
		upd(1, 1, n, contain[v], w);
		upd(1, 1, n, temp2.se, -w);
		}
	}
}

void process(){
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		int x, y, w;
		cin >> x >> y >> w;
		Adj[x].pb({y, w});
		Adj[y].pb({x, w});
	}
	dfs(1, 1);
	for(int i = 1; i <= n; i++){
		rev[p[i]] = i;
	}
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
		int mxx = pos[1], temp = mxx;
		if(i <= k) answer[1] += mx[1];
		vertex[mxx] = mx[1];
		er(1, 1, n, mxx);
		mxx = rev[mxx];
		//white--;
		while(mxx && !vis[mxx]){
			vis[mxx] = 1;
			upd(1, 1, n, l[mxx], r[mxx], edg[mxx]);
			contain[mxx] = temp;
			mxx = par[mxx];
		}
	}
	for(int i = 1; i <= n; i++) os.insert({vertex[i], i});
	build2(1, 1, n);
	dfs_ans(1, 1);
	for(int i = 1; i <= n; i++) cout << answer[i] << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}
 
/*
1 2
1 3
2 4
3 5
2 6
6 7
6 8
*/

Compilation message

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from Main.cpp:2:
Main.cpp: In function 'void dfs_ans(long long int, long long int)':
Main.cpp:145:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  145 |   assert(os.size() == n);
      |          ~~~~~~~~~~^~~~
Main.cpp:153:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  153 |   assert(os.size() == n);
      |          ~~~~~~~~~~^~~~
Main.cpp:163:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  163 |   assert(os.size() == n);
      |          ~~~~~~~~~~^~~~
Main.cpp:167:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  167 |   assert(os.size() == n);
      |          ~~~~~~~~~~^~~~
Main.cpp:138:6: warning: variable 'temp1' set but not used [-Wunused-but-set-variable]
  138 |   ii temp1 = get(1, 1, n, l[v], r[v]);
      |      ^~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct
13 Correct 8 ms 5580 KB Output is correct
14 Correct 11 ms 5708 KB Output is correct
15 Correct 8 ms 5680 KB Output is correct
16 Correct 8 ms 5580 KB Output is correct
17 Correct 8 ms 5580 KB Output is correct
18 Correct 7 ms 5580 KB Output is correct
19 Correct 8 ms 5580 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 33768 KB Output is correct
2 Correct 501 ms 36344 KB Output is correct
3 Correct 462 ms 33652 KB Output is correct
4 Correct 526 ms 33540 KB Output is correct
5 Correct 569 ms 36680 KB Output is correct
6 Correct 520 ms 33596 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 ms 5324 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct
13 Correct 8 ms 5580 KB Output is correct
14 Correct 11 ms 5708 KB Output is correct
15 Correct 8 ms 5680 KB Output is correct
16 Correct 8 ms 5580 KB Output is correct
17 Correct 8 ms 5580 KB Output is correct
18 Correct 7 ms 5580 KB Output is correct
19 Correct 8 ms 5580 KB Output is correct
20 Correct 575 ms 33768 KB Output is correct
21 Correct 501 ms 36344 KB Output is correct
22 Correct 462 ms 33652 KB Output is correct
23 Correct 526 ms 33540 KB Output is correct
24 Correct 569 ms 36680 KB Output is correct
25 Correct 520 ms 33596 KB Output is correct
26 Correct 532 ms 34580 KB Output is correct
27 Correct 529 ms 37336 KB Output is correct
28 Correct 506 ms 38256 KB Output is correct
29 Correct 455 ms 35840 KB Output is correct
30 Correct 533 ms 34120 KB Output is correct
31 Correct 539 ms 35352 KB Output is correct
32 Correct 516 ms 36816 KB Output is correct
33 Correct 548 ms 34376 KB Output is correct
34 Correct 420 ms 34004 KB Output is correct
35 Correct 534 ms 33952 KB Output is correct
36 Correct 512 ms 38080 KB Output is correct