oj.uz

Submission #1039885

# Submission time Handle Problem Language Result Execution time Memory
1039885 2024-07-31T11:26:27 Z 라스무스 뷘터(#11030) Petrol stations (CEOI24_stations) C++17
8 / 100
 175 ms 21664 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();
	}
}

vector<pi> v;
lint ptr, sum;

void dfs_down(int x, int p, int w) {
	lint pptr = ptr;
	lint psum = sum;
	{
		sum += w;
		int npptr = lower_bound(all(v), pi{sum - k, -1}) - v.begin();
		lint cur = v[npptr - 1][1] - v[ptr - 1][1];
		ans[actual[p]] += cur * realsub[x];
		cur += v.back()[1];
		if (v.back()[0] == sum - w)
			v.back()[1] = cur;
		else
			v.push_back({sum - w, cur});
		ptr = npptr;
	}
	for (auto &[w, y] : gph[x]) {
		if (!vis[y] && y != p) {
			dfs_down(y, x, w);
		}
	}
	ptr = pptr;
	sum = psum;
	v.pop_back();
}

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;
			v.clear();
			v.push_back({0, 0});
			for (auto &[subtree, count, remain] : boxofchocolates) {
				if (y[1] == subtree)
					continue;
				v.push_back(pi{remain, count});
			}
			sort(all(v));
			for (int i = 1; i < sz(v); i++)
				v[i][1] += v[i - 1][1];
			ptr = 1;
			sum = k;
			dfs_down(y[1], x, y[0]);
		}
		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 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 2 ms 8796 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 1 ms 8540 KB Output is correct
2 Correct 144 ms 20444 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 144 ms 20444 KB Output is correct
5 Correct 159 ms 20652 KB Output is correct
6 Incorrect 175 ms 21664 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 146 ms 14144 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 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 146 ms 14144 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 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Incorrect 2 ms 8796 KB Output isn't correct
4 Halted 0 ms 0 KB -