Submission #499869

#	Time	Username	Problem	Language	Result	Execution time	Memory
499869		keta_tsimakuridze	Paths (RMI21_paths)	C++14	56 / 100	829 ms	118120 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define ll long long
#define int long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
const ll m = 1e15; // !
int t, h[N], n, k, f[N], ri_[N * 30], le_[N * 30], mx[N][2], idx, b[N];
ll sum[N], ans[N];
struct node {
	ll s;
	int c;
} tree[N * 30];
pii p[N];
vector<pii> V[N], x;
void dfs(int u) {
	x.push_back({h[u], u}); 
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i].f == p[u].f) continue;
		p[V[u][i].f] = {u, V[u][i].s};
		h[V[u][i].f] = h[u] + V[u][i].s;
		dfs(V[u][i].f);
	}
}
int up(int u) {
	int sum = 0;
	while(f[u]) {
		sum += p[u].s;
		f[u] = 0;
		u = p[u].f;
	}
	return sum;
}
int get(int u,ll l, ll r, int k) {
	if(l == r) {
		return k * l;
	}
	int mid = (l + r) >> 1;
	if(tree[ri_[u]].c >= k) return get(ri_[u], mid + 1, r, k);
	return tree[ri_[u]].s + get(le_[u], l, mid, k - tree[ri_[u]].c);
}
void upd(int u,ll id, ll l,ll r,int val) {
	if(l == r) {
		tree[u].c += val;
		tree[u].s += val * l;
		return;
	}
	int mid = (l + r) >> 1;
	if(id <= mid) {
		if(!le_[u]) le_[u] = ++idx;
		upd(le_[u], id, l, mid, val);
	}
	else {
	if(!ri_[u]) ri_[u] = ++idx;
	upd(ri_[u], id, mid + 1, r, val);}
	tree[u].c = tree[le_[u]].c + tree[ri_[u]].c;
	tree[u].s = tree[le_[u]].s + tree[ri_[u]].s;
}
void dfs2(int u) {
	int M = 0, y = 0;
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i].f == p[u].f) continue;
		dfs2(V[u][i].f);
		int v = V[u][i].f;
	
		if(mx[u][0] < mx[v][0] + V[u][i].s) {
			mx[u][1] = mx[u][0];
			mx[u][0] = mx[v][0] + V[u][i].s;
		} else mx[u][1] = max(mx[u][1], mx[v][0] + V[u][i].s);
	}
	
}
void reroot(int u, int p_ = -mod) {
	ans[u] = get(1, 1, m, k);
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i].f == p[u].f) continue;
		// 
		int v = V[u][i].f;
		// mx[v][0] - V[u][i].s gaxdeba
		int x = mx[u][0];
		if(mx[v][0] + V[u][i].s == mx[u][0]) x = mx[u][1];
		x = max(x, p_);
		upd(1, mx[v][0] + V[u][i].s, 1, m, -1);
		upd(1, mx[v][0], 1, m, 1);
		upd(1, x, 1, m, -1); 
		upd(1, x + V[u][i].s, 1, m, 1);
	//	return;
		reroot(v, x + V[u][i].s);
		
		upd(1, mx[v][0] + V[u][i].s, 1, m, 1);
		upd(1, mx[v][0] , 1, m, -1);
		
		upd(1, x, 1, m, 1);
		upd(1, x + V[u][i].s, 1, m, -1);	
	}
	
}
main(){
	cin >> n >> k;
	idx = 1;
	for(int i = 2; i <= n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		V[u].push_back({v, w});
		V[v].push_back({u, w});
		f[i] = 1;
	}
	
	dfs(1); 
	sort(x.rbegin(), x.rend());
	for(int i = 0; i < x.size(); i++) {
		sum[x[i].s] = up(x[i].s);
		upd(1, sum[x[i].s], 1, m, 1);
//		cout << x[i].s <<" __" << sum[x[i].s] << " ";
	}
	dfs2(1);
	reroot(1);
	for(int i = 1; i <= n; i++) cout << ans[i] <<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(long long int)':
Main.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp:62:6: warning: unused variable 'M' [-Wunused-variable]
   62 |  int M = 0, y = 0;
      |      ^
Main.cpp:62:13: warning: unused variable 'y' [-Wunused-variable]
   62 |  int M = 0, y = 0;
      |             ^
Main.cpp: In function 'void reroot(long long int, long long int)':
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:113:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32