oj.uz

답안 #1046105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046105 2024-08-06T10:09:06 Z alex_2008 Petrol stations (CEOI24_stations) C++14
65 / 100
 3500 ms 20500 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];
ll pref[N], people[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);
	}
}
void f(vector <int> indd, vector <int> len) {
	indd.insert(indd.begin(), 0);
	len.insert(len.begin(), 0);
	for (int i = 1; i < n; i++) {
		pref[i] = pref[i - 1] + len[i];
	}
	for (int i = 1; i <= n; i++) {
		people[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if ((pref[n - 1] - pref[i - 1]) <= k) continue;
		int ind = upper_bound(pref + 1, pref + n, pref[i - 1] + k) - pref;
		people[ind] += people[i];
		cnt[indd[ind]] += (people[i] * 1ll * (n - ind));
	}
}
void dfs_0_0(int v, int p) {
	subtree[v] = 1;
	for (auto it : G[v]) {
		if (it.first == p) continue;
		dfs_0_0(it.first, v);
		subtree[v] += subtree[it.first];
	}
}
void dfs(int v, int p, int depth) {
	for (auto it : G[v]) {
		if (it.first == p) continue;
		int c = depth + it.second;
		if (c <= k) dfs(it.first, v, c);
		else {
			cnt[v] += subtree[it.first];
			dfs(it.first, v, it.second);
		}
	}
}
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 });
	}
	if (k <= 10) {	
		rec(1);
		for (int i = 1; i <= n; i++) {
			cout << cnt[i] << "\n";
		}
		return 0;
	}
	if (n <= 1000) {
		for (int i = 1; i <= n; i++) {
			dfs_0_0(i, i);
			dfs(i, i, 0);
		}
		for (int i = 1; i <= n; i++) {
			cout << cnt[i] << "\n";
		}
		return 0;
	}
	vector <int> ind;
	vector <int> len;
	for (int i = 1; i <= n; i++) {
		if ((int)G[i].size() == 1) {
			ind.push_back(i);
			break;
		}
	}
	while ((int)ind.size() != n) {
		int v = ind.back(), p = -1;
		if ((int)ind.size() != 1) p = ind[(int)ind.size() - 2];
		for (auto it : G[v]) {
			if (it.first == p) continue;
			ind.push_back(it.first);
			len.push_back(it.second);
			break;
		}
	}
	f(ind, len);
	reverse(ind.begin(), ind.end()); reverse(len.begin(), len.end());
	f(ind, len);
	for (int i = 1; i <= n; i++) {
		cout << cnt[i] << "\n";
	}
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 21 ms 348 KB Output is correct
7 Correct 18 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 520 KB Output is correct
10 Correct 12 ms 348 KB Output is correct
11 Correct 12 ms 516 KB Output is correct
12 Correct 11 ms 344 KB Output is correct
13 Correct 11 ms 348 KB Output is correct
14 Correct 7 ms 512 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 216 ms 19452 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 216 ms 19452 KB Output is correct
5 Correct 51 ms 7540 KB Output is correct
6 Correct 48 ms 7540 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 195 ms 10952 KB Output is correct
4 Correct 271 ms 20308 KB Output is correct
5 Correct 233 ms 20500 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 172 ms 11348 KB Output is correct
8 Correct 184 ms 11348 KB Output is correct
9 Correct 186 ms 11540 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 195 ms 10952 KB Output is correct
4 Correct 271 ms 20308 KB Output is correct
5 Correct 233 ms 20500 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 172 ms 11348 KB Output is correct
8 Correct 184 ms 11348 KB Output is correct
9 Correct 186 ms 11540 KB Output is correct
10 Correct 107 ms 12392 KB Output is correct
11 Correct 179 ms 11344 KB Output is correct
12 Correct 144 ms 11324 KB Output is correct
13 Correct 134 ms 11212 KB Output is correct
14 Correct 131 ms 11336 KB Output is correct
15 Correct 151 ms 11352 KB Output is correct
16 Correct 46 ms 11640 KB Output is correct

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 10 ms 348 KB Output is correct
6 Correct 21 ms 348 KB Output is correct
7 Correct 18 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 520 KB Output is correct
10 Correct 12 ms 348 KB Output is correct
11 Correct 12 ms 516 KB Output is correct
12 Correct 11 ms 344 KB Output is correct
13 Correct 11 ms 348 KB Output is correct
14 Correct 7 ms 512 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 216 ms 19452 KB Output is correct
17 Correct 51 ms 7540 KB Output is correct
18 Correct 48 ms 7540 KB Output is correct
19 Correct 195 ms 10952 KB Output is correct
20 Correct 271 ms 20308 KB Output is correct
21 Correct 233 ms 20500 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 172 ms 11348 KB Output is correct
24 Correct 184 ms 11348 KB Output is correct
25 Correct 186 ms 11540 KB Output is correct
26 Correct 107 ms 12392 KB Output is correct
27 Correct 179 ms 11344 KB Output is correct
28 Correct 144 ms 11324 KB Output is correct
29 Correct 134 ms 11212 KB Output is correct
30 Correct 131 ms 11336 KB Output is correct
31 Correct 151 ms 11352 KB Output is correct
32 Correct 46 ms 11640 KB Output is correct
33 Execution timed out 3596 ms 5432 KB Time limit exceeded
34 Halted 0 ms 0 KB -