oj.uz

Submission #499869

# Submission time Handle Problem Language Result Execution time Memory
499869 2021-12-29T20:52:06 Z keta_tsimakuridze Paths (RMI21_paths) C++14
56 / 100
 600 ms 118120 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, 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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5324 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 2 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 12 ms 6556 KB Output is correct
9 Correct 8 ms 6864 KB Output is correct
10 Correct 8 ms 6732 KB Output is correct
11 Correct 8 ms 6476 KB Output is correct
12 Correct 8 ms 5724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 12 ms 6556 KB Output is correct
9 Correct 8 ms 6864 KB Output is correct
10 Correct 8 ms 6732 KB Output is correct
11 Correct 8 ms 6476 KB Output is correct
12 Correct 8 ms 5724 KB Output is correct
13 Correct 15 ms 7960 KB Output is correct
14 Correct 14 ms 8652 KB Output is correct
15 Correct 26 ms 8532 KB Output is correct
16 Correct 15 ms 7928 KB Output is correct
17 Correct 11 ms 5972 KB Output is correct
18 Correct 13 ms 7612 KB Output is correct
19 Correct 16 ms 8024 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 3 ms 5324 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 12 ms 6556 KB Output is correct
9 Correct 8 ms 6864 KB Output is correct
10 Correct 8 ms 6732 KB Output is correct
11 Correct 8 ms 6476 KB Output is correct
12 Correct 8 ms 5724 KB Output is correct
13 Correct 15 ms 7960 KB Output is correct
14 Correct 14 ms 8652 KB Output is correct
15 Correct 26 ms 8532 KB Output is correct
16 Correct 15 ms 7928 KB Output is correct
17 Correct 11 ms 5972 KB Output is correct
18 Correct 13 ms 7612 KB Output is correct
19 Correct 16 ms 8024 KB Output is correct
20 Execution timed out 829 ms 118120 KB Time limit exceeded
21 Halted 0 ms 0 KB -