Submission #1036524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036524		model_code	Petrol stations (CEOI24_stations)	C++17	100 / 100	2103 ms	1082960 KiB

Main

// Author: Pepa Minařík
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n;
ll k;

struct tree {
    int sum = 0;
    tree *left_child = nullptr, *right_child = nullptr;

    void extend(ll left, ll right) {
        if (!left_child && left + 1 < right) {
            left_child = new tree();
            right_child = new tree();
        }
    }

	void add(ll kk, ll x, ll left = 0, ll right = (n + 1) * k)
	{
        sum += x;
        if (left + 1 < right) {
            if (kk < (left + right) / 2)
			{
				if (!left_child) left_child = new tree();
                left_child->add(kk, x, left, (left + right) / 2);
			}
            else
			{
				if (!right_child) right_child = new tree();
                right_child->add(kk, x, (left + right) / 2, right);
			}
        }
	}

	int get_sum(ll lq, ll rq, ll left = 0, ll right = (n + 1) * k) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
		ll answer = 0;
		if (left_child)
			answer += left_child->get_sum(lq, rq, left, (left + right) / 2);
		if (right_child)
			answer += right_child->get_sum(lq, rq, (left + right) / 2, right);
        return answer;
    }
};


ll ans[100005];
bool blocked[100005];
int depth[100005], siz[100005], keys[100005], multiplicity[100005];
int pred[100005][20];
ll dist[100005][20];
vector<pair<int, int>> graf[100005];
map<int, vector<pair<int, int>>> key_to_cars[100005];

void stage_up(int v, int f, int d, int l, int key)
{
	depth[v] = d;
	pred[v][0] = f;
	dist[v][0] = l;
	keys[v] = key;
	siz[v] = multiplicity[v] = 1;
	for (int i = 1; i < 20; i++)
	{
		pred[v][i] = pred[pred[v][i-1]][i-1];
		dist[v][i] = dist[v][i-1] + dist[pred[v][i-1]][i-1];
	}
	for (auto u : graf[v])
	{
		if (u.first == f || blocked[u.first]) continue;
		int new_key = key;
		if (d == 0)
			new_key = u.first;
		stage_up(u.first, v, d+1, u.second, new_key);
		siz[v] += siz[u.first];
	}

	int u = v;
	ll dist_from_v = 0;
	for (int i = 19; i >= 0; i--)
	{
		if (dist_from_v + dist[u][i] <= k)
		{
			dist_from_v += dist[u][i];
			u = pred[u][i];
		}
	}
	if (depth[u])
		multiplicity[u] += multiplicity[v];
	else
        key_to_cars[u][keys[v]].push_back({k - dist_from_v, multiplicity[v]});
}

void stage_down(int v, int f, ll dist_from_root, tree *t, int total_size, int key_size)
{
	ans[v] += (multiplicity[v] - 1) * (ll)(total_size - key_size);
	for (auto u : graf[v])
	{
		if (u.first == f || blocked[u.first]) continue;
		if (!dist_from_root)
			for (auto car: key_to_cars[v][keys[u.first]])
				t->add(car.first, -car.second);	
		ll multiplicity_to_add = t->get_sum(dist_from_root, dist_from_root + u.second);
		ans[v] += multiplicity_to_add * (ll)siz[u.first];
        t->add(dist_from_root + k, multiplicity_to_add);
		int new_key_size = depth[v] ? key_size : siz[u.first];
		stage_down(u.first, v, dist_from_root + u.second, t, total_size, new_key_size);
        t->add(dist_from_root + k, -multiplicity_to_add);
		if (!dist_from_root)
			for (auto car: key_to_cars[v][keys[u.first]])
				t->add(car.first, car.second);	
	}
}


int find_centroid(int v, int f, int s)
{
	for (auto u : graf[v])
	{
		if (u.first == f || blocked[u.first]) continue;
		if (siz[u.first] > s/2)
			return find_centroid(u.first, v, s);
	}
	return v;
}

void solve(int v)
{
	stage_up(v, v, 0, 0, -1);
    tree *t = new tree();
	for (auto pair: key_to_cars[v])
		for (auto car : pair.second)
			t->add(car.first, car.second);

	stage_down(v, v, 0, t, siz[v], 0);

	blocked[v] = true;
	for (auto u : graf[v])
	{
		if (blocked[u.first]) continue;
		int c = find_centroid(u.first, v, siz[u.first]);
		solve(c);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	int u, v, l;
	for (int i = 0; i < n-1; i++)
	{
		cin >> u >> v >> l;
		graf[u].push_back({v, l});
		graf[v].push_back({u, l});
	}
	solve(0);

	for (int i = 0; i < n; i++)
		cout << ans[i] << "\n";	
	return 0;
}

• 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