oj.uz

Submission #1046096

# Submission time Handle Problem Language Result Execution time Memory
1046096 2024-08-06T10:04:50 Z alex_2008 Petrol stations (CEOI24_stations) C++14
37 / 100
 232 ms 27988 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
typedef long long ll;
using namespace std;
const int N = 70070;
ll cnt[N];
int subtree[N];
int dp[N][20];
bool used[N];
vector <vector<pair<int, int>>> G;
int n, k;
void dfs_0(int v, int p) {
	subtree[v] = 1;
	for (auto it : G[v]) {
		if (used[it.first] || it.first == p) continue;
		dfs_0(it.first, v);
		subtree[v] += subtree[it.first];
	}
}
int find_centroid(int v) {
	int k = subtree[v];
	int p = v;
	while (1) {
		int new_v = -1;
		for (auto it : G[v]) {
			if (it.first == p || used[it.first]) continue;
			if (2 * subtree[it.first] > k) {
				new_v = it.first;
				break;
			}
		}
		if (new_v == -1) break;
		p = v;
		v = new_v;
	}
	return v;
}
void calc_dp(int v, int p) {
	for (int j = 1; j <= k; j++) {
		dp[v][j] = 0;
	}
	dp[v][0] = 1;
	for (auto it : G[v]) {
		if (it.first == p || used[it.first]) {
			continue;
		}
		calc_dp(it.first, v);
		for (int j = 0; j <= k; j++) {
			int c = j + it.second;
			if (c > k) c = it.second;
			dp[v][c] += dp[it.first][j];
		}
	}
}
void update_1(int v, int p, int len, int sz) {
	for (int j = 0; j <= k; j++) {
		if ((j + len) > k) {
			cnt[v] += (sz * 1ll * dp[v][j]);
		}
	}
	for (auto it : G[v]) {
		if (it.first == p || used[it.first]) {
			continue;
		}
		update_1(it.first, v, it.second, sz);
	}
}
void propogate(int v, int p, vector <int> cur) {
	for (auto it : G[v]) {
		if (it.first == p || used[it.first]) continue;
		vector <int> curr(k + 1);
		for (int j = 0; j <= k; j++) {
			int c = j + it.second;
			if (c > k) {
				cnt[v] += (cur[j] * 1ll * subtree[it.first]);
				c = it.second;
			}
			curr[c] += cur[j];
		}
		propogate(it.first, v, curr);
	}
}
void rec(int v) {
	dfs_0(v, v);
	v = find_centroid(v);
	dfs_0(v, v);

	vector <pair<int, int>> childs;
	for (auto it : G[v]) {
		if (!used[it.first]) {
			childs.push_back(it);
		}
	}
	calc_dp(v, v);

	for (auto it : childs) {
		update_1(it.first, v, it.second, subtree[v] - subtree[it.first]);
	}
;
	for (auto it : childs) {

		for (int j = 0; j <= k; j++) {
			int c = j + it.second;
			if (c > k) c = it.second;
			dp[v][c] -= dp[it.first][j];
		}

		vector <int> cur(k + 1, 0);
		for (int j = 0; j <= k; j++) {
			int c = j + it.second;
			if (c > k) {
				cnt[v] += (dp[v][j] * 1ll * subtree[it.first]);
				c = it.second;
			}
			cur[c] += dp[v][j];
		}
		propogate(it.first, v, cur);
		for (int j = 0; j <= k; j++) {
			int c = j + it.second;
			if (c > k) c = it.second;
			dp[v][c] += dp[it.first][j];
		}
	}

	used[v] = true;
	for (auto it : childs) {
		rec(it.first);
	}
}
int main() {
	cin >> n >> k;
	G.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a++; b++;
		G[a].push_back({ b, c });
		G[b].push_back({ a, c });
	}	
	rec(1);
	for (int i = 1; i <= n; i++) {
		cout << cnt[i] << "\n";
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 13 ms 2652 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 0 ms 2396 KB Output is correct
2 Correct 205 ms 19540 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 205 ms 19540 KB Output is correct
5 Runtime error 56 ms 27988 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 178 ms 11092 KB Output is correct
4 Correct 229 ms 21392 KB Output is correct
5 Correct 232 ms 21940 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 168 ms 12276 KB Output is correct
8 Correct 175 ms 12416 KB Output is correct
9 Correct 176 ms 12372 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 178 ms 11092 KB Output is correct
4 Correct 229 ms 21392 KB Output is correct
5 Correct 232 ms 21940 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 168 ms 12276 KB Output is correct
8 Correct 175 ms 12416 KB Output is correct
9 Correct 176 ms 12372 KB Output is correct
10 Correct 96 ms 13136 KB Output is correct
11 Correct 113 ms 12112 KB Output is correct
12 Correct 113 ms 12268 KB Output is correct
13 Correct 136 ms 12372 KB Output is correct
14 Correct 121 ms 12112 KB Output is correct
15 Correct 123 ms 12116 KB Output is correct
16 Correct 39 ms 12708 KB Output is correct

Subtask #6
0.0 / 35.0

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