oj.uz

Submission #1046172

# Submission time Handle Problem Language Result Execution time Memory
1046172 2024-08-06T11:01:34 Z Tsovak Petrol stations (CEOI24_stations) C++17
37 / 100
 50 ms 29944 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 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 4 ms 5212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 39 ms 27700 KB Output is correct
5 Runtime error 26 ms 24156 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 34 ms 17492 KB Output is correct
4 Correct 41 ms 26964 KB Output is correct
5 Correct 50 ms 29944 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 36 ms 17232 KB Output is correct
8 Correct 36 ms 17104 KB Output is correct
9 Correct 34 ms 17236 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 34 ms 17492 KB Output is correct
4 Correct 41 ms 26964 KB Output is correct
5 Correct 50 ms 29944 KB Output is correct
6 Correct 1 ms 4952 KB Output is correct
7 Correct 36 ms 17232 KB Output is correct
8 Correct 36 ms 17104 KB Output is correct
9 Correct 34 ms 17236 KB Output is correct
10 Correct 30 ms 17404 KB Output is correct
11 Correct 31 ms 17096 KB Output is correct
12 Correct 29 ms 17140 KB Output is correct
13 Correct 35 ms 16976 KB Output is correct
14 Correct 32 ms 16996 KB Output is correct
15 Correct 33 ms 16980 KB Output is correct
16 Correct 27 ms 16196 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Incorrect 4 ms 5212 KB Output isn't correct
4 Halted 0 ms 0 KB -