oj.uz

Submission #499870

# Submission time Handle Problem Language Result Execution time Memory
499870 2021-12-29T20:54:35 Z keta_tsimakuridze Paths (RMI21_paths) C++14
56 / 100
 600 ms 118252 KB 
#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,  n, k, f[N], ri_[N * 30], le_[N * 30], idx;
ll sum[N], ans[N], h[N], mx[N][2];
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);
	}
}
ll up(int u) {
	ll sum = 0;
	while(f[u]) {
		sum += p[u].s;
		f[u] = 0;
		u = p[u].f;
	}
	return sum;
}
ll get(int u,ll l, ll r, int k) {
	if(l == r) {
		return (ll)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, ll 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
		ll 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);
		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(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	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] <<" ";
}

Compilation message

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:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | 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.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 4 ms 5328 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 3 ms 5196 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 4 ms 5328 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 8 ms 6616 KB Output is correct
9 Correct 8 ms 6860 KB Output is correct
10 Correct 8 ms 6772 KB Output is correct
11 Correct 9 ms 6488 KB Output is correct
12 Correct 7 ms 5708 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 4 ms 5328 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 8 ms 6616 KB Output is correct
9 Correct 8 ms 6860 KB Output is correct
10 Correct 8 ms 6772 KB Output is correct
11 Correct 9 ms 6488 KB Output is correct
12 Correct 7 ms 5708 KB Output is correct
13 Correct 13 ms 8012 KB Output is correct
14 Correct 13 ms 8676 KB Output is correct
15 Correct 13 ms 8524 KB Output is correct
16 Correct 12 ms 7884 KB Output is correct
17 Correct 11 ms 5920 KB Output is correct
18 Correct 11 ms 7588 KB Output is correct
19 Correct 15 ms 8008 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 741 ms 118252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
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 4 ms 5328 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 3 ms 5196 KB Output is correct
8 Correct 8 ms 6616 KB Output is correct
9 Correct 8 ms 6860 KB Output is correct
10 Correct 8 ms 6772 KB Output is correct
11 Correct 9 ms 6488 KB Output is correct
12 Correct 7 ms 5708 KB Output is correct
13 Correct 13 ms 8012 KB Output is correct
14 Correct 13 ms 8676 KB Output is correct
15 Correct 13 ms 8524 KB Output is correct
16 Correct 12 ms 7884 KB Output is correct
17 Correct 11 ms 5920 KB Output is correct
18 Correct 11 ms 7588 KB Output is correct
19 Correct 15 ms 8008 KB Output is correct
20 Execution timed out 741 ms 118252 KB Time limit exceeded
21 Halted 0 ms 0 KB -