oj.uz

Submission #1045992

# Submission time Handle Problem Language Result Execution time Memory
1045992 2024-08-06T08:51:35 Z Tsovak Petrol stations (CEOI24_stations) C++17
36 / 100
 3441 ms 14940 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];
}

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[u]));

	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;
	}


	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
18.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 Correct 1949 ms 11220 KB Output is correct
4 Correct 2958 ms 11236 KB Output is correct
5 Correct 3209 ms 11252 KB Output is correct
6 Correct 3104 ms 11352 KB Output is correct
7 Correct 3187 ms 11356 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3416 ms 11236 KB Output is correct
10 Correct 3215 ms 11240 KB Output is correct
11 Correct 3406 ms 11236 KB Output is correct
12 Correct 3314 ms 11236 KB Output is correct
13 Correct 3441 ms 11100 KB Output is correct
14 Correct 3265 ms 11356 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
10.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 4956 KB Output is correct
4 Correct 28 ms 14824 KB Output is correct
5 Correct 29 ms 14940 KB Output is correct
6 Correct 43 ms 14484 KB Output is correct

Subtask #4
0.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 Incorrect 21 ms 9808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.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 Incorrect 21 ms 9808 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Correct 1949 ms 11220 KB Output is correct
4 Correct 2958 ms 11236 KB Output is correct
5 Correct 3209 ms 11252 KB Output is correct
6 Correct 3104 ms 11352 KB Output is correct
7 Correct 3187 ms 11356 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 3416 ms 11236 KB Output is correct
10 Correct 3215 ms 11240 KB Output is correct
11 Correct 3406 ms 11236 KB Output is correct
12 Correct 3314 ms 11236 KB Output is correct
13 Correct 3441 ms 11100 KB Output is correct
14 Correct 3265 ms 11356 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 28 ms 14824 KB Output is correct
17 Correct 29 ms 14940 KB Output is correct
18 Correct 43 ms 14484 KB Output is correct
19 Incorrect 21 ms 9808 KB Output isn't correct
20 Halted 0 ms 0 KB -