Submission #509759

#	Time	Username	Problem	Language	Result	Execution time	Memory
509759		minhcool	Paths (RMI21_paths)	C++17	100 / 100	575 ms	38256 KiB

Main

#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 (stderr)

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