Submission #1042213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042213		Lucpp	Petrol stations (CEOI24_stations)	C++17	100 / 100	1392 ms	189180 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = long long;

constexpr int NODES = 11e6;
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
• Subtask 1: 18 / 18
• Subtask 2: 8 / 8
• Subtask 3: 10 / 10
• Subtask 4: 12 / 12
• Subtask 5: 17 / 17
• Subtask 6: 35 / 35