oj.uz

Submission #1046173

# Submission time Handle Problem Language Result Execution time Memory
1046173 2024-08-06T11:02:02 Z Tsovak Petrol stations (CEOI24_stations) C++17
65 / 100
 3180 ms 17492 KB 
// -------------------- Includes -------------------- //
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <stdlib.h>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <tuple>
#include <utility>
#include <cassert>
#include <assert.h>
#include <climits>
#include <limits.h>
#include <ctime>
#include <time.h>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Functions -------------------- //

void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return;
}

void precision(int x)
{
	cout << fixed << setprecision(x);
	return;
}

ll gcd0(ll a, ll b)
{
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

ll lcm0(ll a, ll b)
{
	return a / gcd0(a, b) * b;
}

bool is_prime(ll a)
{
	if (a == 1) return false;
	for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false;
	return true;
}

bool is_square(ll a)
{
	ll b = ll(sqrtl(ld(a)));
	return (b * b == a);
}

bool is_cube(ll a)
{
	ll b = ll(cbrtl(ld(a)));
	return (b * b * b == a);
}

int digit_sum(ll a)
{
	int sum = 0;
	while (a) {
		sum += int(a % 10);
		a /= 10;
	}
	return sum;
}

ll binpow(ll a, int b)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans *= a;
		b >>= 1;
		a *= a;
	}
	return ans;
}

ll binpow_mod(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}

ll factorial(int a)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans *= ll(i);
	return ans;
}

ll factorial_mod(int a, ll mod)
{
	ll ans = 1;
	for (int i = 2; i <= a; i++) ans = (ans * ll(i)) % mod;
	return ans;
}

// -------------------- Solution -------------------- //

const int N = 70005;
int a[N];
ll b[N], pref[N];
vector<pr<int, int>> g[N];
int sz[N];
ll cnt[1005][1005];
ll ans[N];
int n, k;

void dfs(int u, int p = 0)
{
	int i, j;
	int v;

	for (i = 0; i < sz(g[u]); i++) {
		v = g[u][i].ff;

		if (v == p) continue;

		dfs(v, u);
		sz[u] += sz[v];

		for (j = 0; j < g[u][i].ss; j++) cnt[u][k - g[u][i].ss] += cnt[v][j];
		for (j = g[u][i].ss; j <= k; j++) cnt[u][j - g[u][i].ss] += cnt[v][j];
	}
	sz[u]++;
	cnt[u][k]++;

	return;
}

void dfs2(int u, int p, int id)
{
	int i, j;
	int v;

	a[id] = u;

	for (i = 0; i < sz(g[u]); i++) {
		v = g[u][i].ff;

		if (v == p) continue;

		b[id] = g[u][i].ss;

		dfs2(v, u, id + 1);
	}

	return;
}

ll op[N];

ll qry(int l, int r)
{
	return pref[r] - pref[l - 1];
}

ll cn[N][15];
ll ncn[15];

void dfs3(int u, int p = 0)
{
	int i, j;
	int v;

	for (i = 0; i < sz(g[u]); i++) {
		v = g[u][i].ff;

		if (v == p) continue;

		dfs3(v, u);
		sz[u] += sz[v];

		for (j = 0; j < g[u][i].ss; j++) cn[u][k - g[u][i].ss] += cn[v][j];
		for (j = g[u][i].ss; j <= k; j++) cn[u][j - g[u][i].ss] += cn[v][j];
	}
	sz[u]++;
	cn[u][k]++;

	return;
}

void dfs4(int u, int p, int l)
{
	int i, j;
	int v;

	ll c;

	g[u].pb(mpr(0, l));

	for (j = 0; j < l; j++) cn[u][k - l] += cn[0][j];
	for (j = l; j <= k; j++) cn[u][j - l] += cn[0][j];

	for (i = 0; i < sz(g[u]); i++) {
		v = g[u][i].ff;

		if (v == p) continue;

		for (j = 0; j < g[u][i].ss; j++) cn[u][k - g[u][i].ss] -= cn[v][j];
		for (j = g[u][i].ss; j <= k; j++) cn[u][j - g[u][i].ss] -= cn[v][j];

		c = 0;
		for (j = 0; j < g[u][i].ss; j++) c += cn[u][j];

		ans[u] += c * ll(sz[v]);

		for (j = 0; j < g[u][i].ss; j++) cn[u][k - g[u][i].ss] += cn[v][j];
		for (j = g[u][i].ss; j <= k; j++) cn[u][j - g[u][i].ss] += cn[v][j];
	}

	for (j = 0; j < l; j++) cn[u][k - l] -= cn[0][j];
	for (j = l; j <= k; j++) cn[u][j - l] -= cn[0][j];

	g[u].popb();

	vector<int> vg(15);
	for (i = 0; i < 15; i++) vg[i] = cn[0][i];

	for (j = 0; j <= k; j++) ncn[j] = 0;

	for (j = 0; j < l; j++) ncn[k - l] += cn[0][j];
	for (j = l; j <= k; j++) ncn[j - l] += cn[0][j];

	for (j = 0; j <= k; j++) cn[0][j] = ncn[j] + cn[u][j];

	sz[0] += sz[u];


	for (i = 0; i < sz(g[u]); i++) {
		v = g[u][i].ff;

		if (v == p) continue;

		for (j = 0; j < g[u][i].ss; j++) cn[0][k - g[u][i].ss] -= cn[v][j];
		for (j = g[u][i].ss; j <= k; j++) cn[0][j - g[u][i].ss] -= cn[v][j];

		sz[0] -= sz[v];

		dfs4(v, u, g[u][i].ss);
		
		sz[0] += sz[v];

		for (j = 0; j < g[u][i].ss; j++) cn[0][k - g[u][i].ss] += cn[v][j];
		for (j = g[u][i].ss; j <= k; j++) cn[0][j - g[u][i].ss] += cn[v][j];
	}

	for (i = 0; i < 15; i++) cn[0][i] = vg[i];
	sz[0] -= sz[u];

	return;
}

void solve()
{
	int i, j;

	cin >> n >> k;

	int u, v, l;

	for (i = 1; i < n; i++) {
		cin >> u >> v >> l;

		g[u + 1].pb(mpr(v + 1, l));
		g[v + 1].pb(mpr(u + 1, l));
	}

	if (n <= 1000 && k <= 1000) {
		ll c;

		for (u = 1; u <= n; u++) {
			memset(sz, 0, sizeof(sz));
			for (i = 1; i <= n; i++) memset(cnt[i], 0, sizeof(sz));

			dfs(u);

			for (i = 0; i < sz(g[u]); i++) {
				v = g[u][i].ff;

				for (j = 0; j < g[u][i].ss; j++) cnt[u][k - g[u][i].ss] -= cnt[v][j];
				for (j = g[u][i].ss; j <= k; j++) cnt[u][j - g[u][i].ss] -= cnt[v][j];

				c = 0;
				for (j = 0; j < g[u][i].ss; j++) c += cnt[u][j];

				ans[u] += c * ll(sz[v]);

				for (j = 0; j < g[u][i].ss; j++) cnt[u][k - g[u][i].ss] += cnt[v][j];
				for (j = g[u][i].ss; j <= k; j++) cnt[u][j - g[u][i].ss] += cnt[v][j];
			}
		}

		for (i = 1; i <= n; i++) cout << ans[i] << "\n";

		return;
	}

	int d = 0;
	for (i = 1; i <= n; i++) d = max(d, sz(g[i]));

	if (d <= 2) {
		for (i = 1; i <= n; i++) {
			if (sz(g[i]) == 1) {
				dfs2(i, 0, 1);
				break;
			}
		}
		b[n] = MAXL;

		for (i = 1; i <= n; i++) {
			pref[i] = pref[i - 1] + b[i];
			op[i] = 1;
		}

		int l, r, mid;

		for (i = 1; i < n; i++) {
			l = i + 1; r = n;

			while (l < r) {
				mid = (l + r) / 2;

				if (qry(i, mid) <= ll(k)) l = mid + 1;
				else r = mid;
			}

			ans[a[l]] += op[i] * ll(n - l);
			op[l] += op[i];
		}

		// ---------------------

		for (i = 1; i <= n / 2; i++) swap(a[i], a[n + 1 - i]);
		for (i = 1; i <= (n - 1) / 2; i++) swap(b[i], b[n - i]);

		for (i = 1; i <= n; i++) {
			pref[i] = pref[i - 1] + b[i];
			op[i] = 1;
		}

		for (i = 1; i < n; i++) {
			l = i + 1; r = n;

			while (l < r) {
				mid = (l + r) / 2;

				if (qry(i, mid) <= ll(k)) l = mid + 1;
				else r = mid;
			}

			ans[a[l]] += op[i] * ll(n - l);
			op[l] += op[i];
		}

		for (i = 1; i <= n; i++) cout << ans[i] << "\n";

		return;
	}

	dfs3(1, 0);

	dfs4(1, 0, -1);

	for (i = 1; i <= n; i++) cout << ans[i] << "\n";

	return;
}

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

	int tests = 1, tc;
	//cin >> tests;
	for (tc = 1; tc <= tests; tc++) {
		solve();
	}

	return 0;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

Compilation message

Main.cpp: In function 'void dfs2(int, int, int)':
Main.cpp:217:9: warning: unused variable 'j' [-Wunused-variable]
  217 |  int i, j;
      |         ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1749 ms 11100 KB Output is correct
4 Correct 2789 ms 11240 KB Output is correct
5 Correct 3156 ms 11100 KB Output is correct
6 Correct 2981 ms 11356 KB Output is correct
7 Correct 2948 ms 11212 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3103 ms 11276 KB Output is correct
10 Correct 3027 ms 11096 KB Output is correct
11 Correct 3137 ms 11248 KB Output is correct
12 Correct 3180 ms 11100 KB Output is correct
13 Correct 3127 ms 11100 KB Output is correct
14 Correct 3018 ms 11256 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 27 ms 15764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 27 ms 15764 KB Output is correct
5 Correct 34 ms 15452 KB Output is correct
6 Correct 25 ms 15192 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 34 ms 17488 KB Output is correct
4 Correct 24 ms 15452 KB Output is correct
5 Correct 23 ms 15000 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 35 ms 17280 KB Output is correct
8 Correct 36 ms 17080 KB Output is correct
9 Correct 33 ms 17348 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 34 ms 17488 KB Output is correct
4 Correct 24 ms 15452 KB Output is correct
5 Correct 23 ms 15000 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 35 ms 17280 KB Output is correct
8 Correct 36 ms 17080 KB Output is correct
9 Correct 33 ms 17348 KB Output is correct
10 Correct 35 ms 17492 KB Output is correct
11 Correct 30 ms 17172 KB Output is correct
12 Correct 37 ms 17144 KB Output is correct
13 Correct 41 ms 16976 KB Output is correct
14 Correct 33 ms 16976 KB Output is correct
15 Correct 33 ms 16976 KB Output is correct
16 Correct 22 ms 16336 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1749 ms 11100 KB Output is correct
4 Correct 2789 ms 11240 KB Output is correct
5 Correct 3156 ms 11100 KB Output is correct
6 Correct 2981 ms 11356 KB Output is correct
7 Correct 2948 ms 11212 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3103 ms 11276 KB Output is correct
10 Correct 3027 ms 11096 KB Output is correct
11 Correct 3137 ms 11248 KB Output is correct
12 Correct 3180 ms 11100 KB Output is correct
13 Correct 3127 ms 11100 KB Output is correct
14 Correct 3018 ms 11256 KB Output is correct
15 Correct 1 ms 4952 KB Output is correct
16 Correct 27 ms 15764 KB Output is correct
17 Correct 34 ms 15452 KB Output is correct
18 Correct 25 ms 15192 KB Output is correct
19 Correct 34 ms 17488 KB Output is correct
20 Correct 24 ms 15452 KB Output is correct
21 Correct 23 ms 15000 KB Output is correct
22 Correct 1 ms 4956 KB Output is correct
23 Correct 35 ms 17280 KB Output is correct
24 Correct 36 ms 17080 KB Output is correct
25 Correct 33 ms 17348 KB Output is correct
26 Correct 35 ms 17492 KB Output is correct
27 Correct 30 ms 17172 KB Output is correct
28 Correct 37 ms 17144 KB Output is correct
29 Correct 41 ms 16976 KB Output is correct
30 Correct 33 ms 16976 KB Output is correct
31 Correct 33 ms 16976 KB Output is correct
32 Correct 22 ms 16336 KB Output is correct
33 Runtime error 18 ms 14172 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -