Submission #1043753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043753		Tob	Petrol stations (CEOI24_stations)	C++14	100 / 100	589 ms	18508 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 7e4 + 7;

int n, k;
int siz[N], gt[N], bio[N], dp[N], dp2[N], pa[N];
ll ps[N], res[N];
vector <pii> adj[N];
vector <int> v, u;

int ind(vector <ll>& v_, ll x) {return lower_bound(all(v_), x)-v_.begin();}

struct F {
	vector <int> fen;
	vector <ll> g;
	void init(vector <ll>& h) {
		fen.clear(); g.clear();
		sort(all(h)); h.erase(unique(all(h)), h.end());
		g = h;
		fen.resize(g.size(), 0);
	}
	void add(ll x, int val) {
		x = ind(g, x);
		for (x++; x <= g.size(); x += x & -x) fen[x-1] += val;
	}
	int get(int x) {
		int out = 0;
		for (x++; x; x -= x & -x) out += fen[x-1];
		return out;
	}
	int query(ll l, ll r) {
		l = ind(g, l)-1; r = ind(g, r+1)-1;
		return get(r)-get(l);
	}
} f;

int dfs(int x, int o = 0, int p = -1) {
	if (o) v.pb(x);
	u.pb(x);
	pa[x] = p;
	
	int lo = 0, hi = u.size()-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (ps[x]-ps[u[mid]] <= k) hi = mid;
		else lo = mid+1;
	}
	gt[x] = u[lo];
	dp[x] = 0;
	
	siz[x] = 1;
	for (auto y : adj[x]) if (y.F != p && !bio[y.F]) {
		ps[y.F] = ps[x] + y.S;
		siz[x] += dfs(y.F, o, x);
	}
	
	dp[u[lo]] += dp[x]+1;
	u.pop_back();
	return siz[x];
}

void dfs2(int x, int p = -1) {
	dp2[x] = f.query(ps[p], ps[x]-1);
	f.add(ps[p]+k, dp2[x]);
	for (auto y : adj[x]) if (y.F != p && !bio[y.F]) dfs2(y.F, x);
	f.add(ps[p]+k, -dp2[x]);
}

void vdfs(int x, int p = -1) {
	v.pb(x);
	for (auto y : adj[x]) if (y.F != p && !bio[y.F]) vdfs(y.F, x);
}

int cent(int x, int m, int p = -1) {
	for (auto y : adj[x]) if (y.F != p && !bio[y.F] && siz[y.F] > m/2) return cent(y.F, m, x);
	return x;
}

void rek(int x) {
	dfs(x);
	int m = siz[x];
	x = cent(x, m);
	ps[x] = 0;
	dfs(x);
	
	for (auto y : adj[x]) {
		if (bio[y.F]) continue;
		vdfs(y.F, x);
		vector <ll> g;
		for (auto z : v) {
			g.pb(k-ps[z]);
			g.pb(ps[pa[z]]+k);
		}
		f.init(g);
		for (auto z : v) {
			res[z] += (ll)dp[z]*(m-siz[y.F]);
			if (ps[z] <= k) f.add(k-ps[z], dp[z]+1);
		}
		dfs2(y.F, x);
		for (auto z : v) res[pa[z]] -= (ll)dp2[z]*siz[z];
		v.clear();
	}
	vector <ll> g;
	for (auto y : adj[x]) if (!bio[y.F]) vdfs(y.F, x);
	g.pb(k);
	for (auto y : v) {
		g.pb(k-ps[y]);
		g.pb(ps[pa[y]]+k);
	}
	f.init(g);
	f.add(k, 1);
	for (auto y : v) if (ps[y] <= k) f.add(k-ps[y], dp[y]+1);
	for (auto y : adj[x]) if (!bio[y.F]) dfs2(y.F, x);
	for (auto y : v) res[pa[y]] += (ll)dp2[y]*siz[y];
	v.clear();
	
	bio[x] = 1;
	for (auto y : adj[x]) if (!bio[y.F]) rek(y.F);
}

int main () {
	FIO;
	cin >> n >> k;
	
	for (int i = 0; i < n-1; i++) {
		int x, y, w; cin >> x >> y >> w;
		adj[x].pb({y, w});
		adj[y].pb({x, w});
	}
	
	rek(0);
	
	for (int i = 0; i < n; i++) cout << res[i] << "\n";

	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void first::add(ll, int)':
Main.cpp:35:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (x++; x <= g.size(); x += x & -x) fen[x-1] += val;
      |             ~~^~~~~~~~~~~

• 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