oj.uz

Submission #1045889

# Submission time Handle Problem Language Result Execution time Memory
1045889 2024-08-06T08:20:41 Z Tsovak Petrol stations (CEOI24_stations) C++17
18 / 100
 3348 ms 25684 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;
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 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));
	}

	/*dfs(2);
	for (i = 1; i <= n; i++) {
		for (j = 0; j <= k; j++) cout << cnt[i][j] << ' ';
		cout << "\n";
	}*/

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

void precalc()
{
	return;
}

int main()
{
	fastio();

	precalc();

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

	return 0;
}

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 1777 ms 10832 KB Output is correct
4 Correct 2834 ms 10640 KB Output is correct
5 Correct 3333 ms 10832 KB Output is correct
6 Correct 2987 ms 10768 KB Output is correct
7 Correct 2998 ms 10764 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 3282 ms 10660 KB Output is correct
10 Correct 3170 ms 10664 KB Output is correct
11 Correct 3348 ms 10584 KB Output is correct
12 Correct 3341 ms 10588 KB Output is correct
13 Correct 3268 ms 10588 KB Output is correct
14 Correct 3170 ms 10664 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Runtime error 24 ms 25660 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Runtime error 24 ms 25660 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Runtime error 25 ms 25684 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Runtime error 25 ms 25684 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 1 ms 4188 KB Output is correct
3 Correct 1777 ms 10832 KB Output is correct
4 Correct 2834 ms 10640 KB Output is correct
5 Correct 3333 ms 10832 KB Output is correct
6 Correct 2987 ms 10768 KB Output is correct
7 Correct 2998 ms 10764 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 3282 ms 10660 KB Output is correct
10 Correct 3170 ms 10664 KB Output is correct
11 Correct 3348 ms 10584 KB Output is correct
12 Correct 3341 ms 10588 KB Output is correct
13 Correct 3268 ms 10588 KB Output is correct
14 Correct 3170 ms 10664 KB Output is correct
15 Correct 1 ms 4184 KB Output is correct
16 Runtime error 24 ms 25660 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -