oj.uz

Submission #509751

# Submission time Handle Problem Language Result Execution time Memory
509751 2022-01-14T09:21:39 Z minhcool Paths (RMI21_paths) C++17
36 / 100
 600 ms 37768 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";
		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);
		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

Main.cpp: In function 'void dfs_ans(long long int, long long int)':
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 2 ms 5068 KB Output is correct
2 Correct 2 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 2 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 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 2 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 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 8 ms 5324 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5068 KB Output is correct
2 Correct 2 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 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 8 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 8 ms 5708 KB Output is correct
15 Correct 9 ms 5708 KB Output is correct
16 Correct 8 ms 5580 KB Output is correct
17 Incorrect 9 ms 5604 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 33648 KB Output is correct
2 Correct 524 ms 37768 KB Output is correct
3 Correct 476 ms 34240 KB Output is correct
4 Execution timed out 608 ms 34596 KB Time limit exceeded
5 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 2 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 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 8 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 8 ms 5708 KB Output is correct
15 Correct 9 ms 5708 KB Output is correct
16 Correct 8 ms 5580 KB Output is correct
17 Incorrect 9 ms 5604 KB Output isn't correct
18 Halted 0 ms 0 KB -