oj.uz

Submission #1039838

# Submission time Handle Problem Language Result Execution time Memory
1039838 2024-07-31T10:17:45 Z 라스무스 뷘터(#11030) Petrol stations (CEOI24_stations) C++17
38 / 100
 3500 ms 1530080 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
const int MAXN = 140005;

lint k, ans[MAXN];
int actual[MAXN];

vector<pi> gph[MAXN];
vector<int> dfn;
int vis[MAXN], sz[MAXN], msz[MAXN];

void dfs(int x, int p = -1) {
	dfn.push_back(x);
	sz[x] = 1, msz[x] = 0;
	for (auto &y : gph[x]) {
		if (y[1] != p && !vis[y[1]]) {
			dfs(y[1], x);
			sz[x] += sz[y[1]];
			msz[x] = max(msz[x], sz[y[1]]);
		}
	}
}

int get_center(int x) {
	dfn.clear();
	dfs(x);
	pi ret{int(1e9), -1};
	for (auto &x : dfn) {
		int w = max(sz(dfn) - sz[x], msz[x]);
		ret = min(ret, pi{w, x});
	}
	return ret[1];
}

vector<lint> stk;
vector<int> nodes, din;

int parent[MAXN], label[MAXN], subcnt[MAXN], realsub[MAXN];
lint depth[MAXN];

void dfs_count(int x, int p = -1, int subnum = -1) {
	subcnt[x] = 1; // TODO: change for non-binary
	realsub[x] = 1;
	label[x] = (subnum == -1 ? x : subnum);
	if (subnum != -1) {
		int pos = lower_bound(all(stk), stk.back() - k) - stk.begin();
		parent[x] = nodes[pos];
	}
	din.push_back(x);
	for (auto &[w, y] : gph[x]) {
		if (y == p || vis[y])
			continue;
		lint bk = stk.back() + w;
		stk.push_back(bk);
		nodes.push_back(y);
		depth[y] = depth[x] + w;
		dfs_count(y, x, subnum == -1 ? y : subnum);
		realsub[x] += realsub[y];
		stk.pop_back();
		nodes.pop_back();
	}
}

map<lint, lint> reduce(map<lint, lint> mp, lint w, int pv, lint sub) {
	int cur = 0;
	while (sz(mp) && mp.begin()->first < w) {
		cur += mp.begin()->second;
		mp.erase(mp.begin());
	}
	map<lint, lint> mp2;
	swap(mp2, mp);
	for (auto &[k, v] : mp2)
		mp[k - w] += v;
	if (cur > 0) {
		ans[actual[pv]] += cur * sub;
		mp[k - w] += cur;
	}
	return mp;
}

void dfs_down(int x, int p, map<lint, lint> &mp) {
	for (auto &[w, y] : gph[x]) {
		if (!vis[y] && y != p) {
			auto mp2 = reduce(mp, w, x, realsub[y]);
			dfs_down(y, x, mp2);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		gph[u].push_back({w, v});
		gph[v].push_back({w, u});
	}
	iota(actual, actual + n, 0);
	queue<int> que;
	que.push(0);
	while (sz(que)) {
		auto x = que.front();
		que.pop();
		x = get_center(x);
		//	cout << "cent" << x << endl;
		vis[x] = 1;
		depth[x] = 0;
		stk = {0};
		nodes = {x};
		din.clear();
		dfs_count(x);
		reverse(all(din));
		for (auto &v : din) {
			if (v != x) {
				subcnt[parent[v]] += subcnt[v];
			}
		}
		vector<array<lint, 3>> boxofchocolates;
		for (auto &v : din) {
			if (v == x)
				boxofchocolates.push_back({x, 1, k});
			else if (parent[v] == x) {
				boxofchocolates.push_back({label[v], subcnt[v], k - depth[v]});
			}
		}
		int total = 0;
		map<int, int> mp;
		for (auto &[subtree, count, remain] : boxofchocolates) {
			//	cout << subtree << " " << remain << " " << count << endl;
			mp[subtree] += count;
			total += count;
		}
		for (auto &v : din) {
			if (v != x) {
				ans[actual[v]] += 1ll * (total - mp[label[v]]) * (subcnt[v] - 1);
			}
		}
		for (auto &y : gph[x]) {
			if (vis[y[1]])
				continue;
			map<lint, lint> mp;
			for (auto &[subtree, count, remain] : boxofchocolates) {
				if (y[1] == subtree)
					continue;
				mp[remain] += count;
			}
			mp = reduce(mp, y[0], x, realsub[y[1]]);
			dfs_down(y[1], x, mp);
		}
		for (auto &y : gph[x]) {
			if (!vis[y[1]]) {
				que.push(y[1]);
			}
		}
	}
	for (int i = 0; i < n; i++)
		cout << ans[i] << "\n";
}

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 24 ms 9072 KB Output is correct
4 Correct 13 ms 8840 KB Output is correct
5 Correct 19 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 3 ms 8776 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 36 ms 8796 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8672 KB Output is correct
2 Correct 245 ms 25164 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8672 KB Output is correct
4 Correct 245 ms 25164 KB Output is correct
5 Correct 289 ms 25508 KB Output is correct
6 Execution timed out 3571 ms 1530080 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 252 ms 15076 KB Output is correct
4 Correct 275 ms 24904 KB Output is correct
5 Correct 249 ms 26048 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 192 ms 15268 KB Output is correct
8 Correct 201 ms 15316 KB Output is correct
9 Correct 198 ms 15204 KB Output is correct

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 252 ms 15076 KB Output is correct
4 Correct 275 ms 24904 KB Output is correct
5 Correct 249 ms 26048 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 192 ms 15268 KB Output is correct
8 Correct 201 ms 15316 KB Output is correct
9 Correct 198 ms 15204 KB Output is correct
10 Execution timed out 3532 ms 16392 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 24 ms 9072 KB Output is correct
4 Correct 13 ms 8840 KB Output is correct
5 Correct 19 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 3 ms 8776 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 36 ms 8796 KB Output is correct
15 Correct 1 ms 8672 KB Output is correct
16 Correct 245 ms 25164 KB Output is correct
17 Correct 289 ms 25508 KB Output is correct
18 Execution timed out 3571 ms 1530080 KB Time limit exceeded
19 Halted 0 ms 0 KB -