oj.uz

Submission #1042198

# Submission time Handle Problem Language Result Execution time Memory
1042198 2024-08-02T15:56:28 Z Lucpp Petrol stations (CEOI24_stations) C++17
26 / 100
 745 ms 251472 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = long long;

constexpr int NODES = 7e6;
constexpr ll MAX = 1ll << 46;
ll seg[NODES];
int L[NODES], R[NODES];
int nxtNode = 1;

int upd(ll p, ll x, int i, ll l = 0, ll r = MAX){
	int node = nxtNode++;
	seg[node] = seg[i];
	L[node] = L[i];
	R[node] = R[i];
	if(l+1 == r) seg[node] += x;
	else{
		ll m = (l + r) / 2;
		if(p < m) L[node] = upd(p, x, L[i], l, m);
		else R[node] = upd(p, x, R[i], m, r);
		seg[node] = seg[L[node]] + seg[R[node]];
	}
	return node;
}

ll qry(ll ql, ll qr, int i, ll l = 0, ll r = MAX){
	if(i == 0) return 0;
	if(ql <= l && r <= qr) return seg[i];
	if(r <= ql || qr <= l) return 0;
	ll m = (l + r) / 2;
	return qry(ql, qr, L[i], l, m) + qry(ql, qr, R[i], m, r);
}


vector<vector<pair<int, ll>>> g;
ll k;
vector<ll> ans;

vector<int> sub;
vector<vector<pair<ll, int>>> segInit;
vector<int> cars;
vector<pair<ll, int>> depthHist;

void subDfs(int u, int par){
	sub[u] = 1;
	for(auto [v, len] : g[u]){
		if(v == par) continue;
		subDfs(v, u);
		sub[u] += sub[v];
	}
}

int findCent(int u, int par, int want){
	for(auto [v, len] : g[u]){
		if(v != par && sub[v] > want) return findCent(v, u, want);
	}
	return u;
}

void goUp(int u, int par, ll depth, int start, ll factor){
	depthHist.emplace_back(depth, u);
	cars[u] = 0;
	for(auto [v, len] : g[u]){
		if(v == par) continue;
		goUp(v, u, depth + len, start, factor);
	}
	ans[u] += cars[u] * factor;
	cars[u]++;
	if(depth <= k) segInit[start].emplace_back(depth, cars[u]);
	else{
		auto it = lower_bound(all(depthHist), make_pair(depth - k, -1));
		cars[it->second] += cars[u];
	}
	depthHist.pop_back();
}

void goDown(int u, int par, ll depth, ll parLen, int node){
	ll cnt = qry(max(0ll, depth-k-parLen), depth-k, node);
	ans[par] += cnt * sub[u];
	node = upd(depth - parLen, cnt, node);
	for(auto [v, len] : g[u]){
		if(v == par) continue;
		goDown(v, u, depth+len, len, node);
	}
}

void solve(int s){
	if(g[s].empty()) return;
	nxtNode = 1;
	subDfs(s, -1);
	int cent = findCent(s, -1, sub[s]/2);
	subDfs(cent, -1);
	// cerr << cent << "\n";
	int node = 0;
	for(auto [u, len] : g[cent]){
		segInit[u].clear();
		goUp(u, cent, len, u, sub[cent] - sub[u]);
		for(auto [d, cnt] : segInit[u]){
			node = upd(k-d, cnt, node);
		}
	}
	node = upd(k, 1, node);
	// for(ll x : ans) cerr << x << " ";
	// cerr << "\n";
	for(auto [u, len] : g[cent]){
		int myNode = node;
		for(auto [d, cnt] : segInit[u]){
			myNode = upd(k-d, -cnt, myNode);
		}
		goDown(u, cent, k+len, len, myNode);
	}
	// for(ll x : ans) cerr << x << " ";
	// cerr << "\n";
	vector<int> childs;
	for(auto [u, len] : g[cent]) childs.push_back(u);
	for(int u : childs){
		for(auto it = g[u].begin(); it != g[u].end(); it++){
			if(it->first == cent){
				g[u].erase(it);
				break;
			}
		}
	}
	g[cent].clear();
	for(int u : childs){
		solve(u);
	}
}
	
int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n >> k;
	g.resize(n);
	for(int i = 0; i < n-1; i++){
		int u, v; ll len;
		cin >> u >> v >> len;
		g[u].emplace_back(v, len);
		g[v].emplace_back(u, len);
	}
	ans.resize(n);
	sub.resize(n);
	segInit.resize(n);
	cars.resize(n);
	solve(0);
	for(ll x : ans) cout << x << "\n";
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 5980 KB Output is correct
4 Correct 8 ms 6268 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 7 ms 3420 KB Output is correct
7 Correct 9 ms 6320 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 3436 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 5 ms 3244 KB Output is correct
12 Correct 4 ms 3416 KB Output is correct
13 Correct 5 ms 3420 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 655 ms 68768 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 655 ms 68768 KB Output is correct
5 Correct 704 ms 72392 KB Output is correct
6 Runtime error 217 ms 249800 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 606 ms 68952 KB Output is correct
4 Correct 745 ms 72140 KB Output is correct
5 Runtime error 180 ms 251472 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 606 ms 68952 KB Output is correct
4 Correct 745 ms 72140 KB Output is correct
5 Runtime error 180 ms 251472 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 5980 KB Output is correct
4 Correct 8 ms 6268 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 7 ms 3420 KB Output is correct
7 Correct 9 ms 6320 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 3436 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 5 ms 3244 KB Output is correct
12 Correct 4 ms 3416 KB Output is correct
13 Correct 5 ms 3420 KB Output is correct
14 Correct 2 ms 6236 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 655 ms 68768 KB Output is correct
17 Correct 704 ms 72392 KB Output is correct
18 Runtime error 217 ms 249800 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -