oj.uz

답안 #1039913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039913 2024-07-31T12:10:01 Z 라스무스 뷘터(#11030) Petrol stations (CEOI24_stations) C++17
48 / 100
 3500 ms 23484 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 = -1;
		{
			int s = 1, e = sz(v);
			while (s != e) {
				int m = (s + e) / 2;
				if (v[m][0] < sum - k)
					s = m + 1;
				else
					e = m;
			}
			npptr = s;
		}
		assert(npptr >= ptr);
		lint cur = v[npptr - 1][1] - v[ptr - 1][1];
		ans[actual[p]] += cur * realsub[x];
		cur += v.back()[1];
		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

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

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 4856 KB Output is correct
8 Correct 2 ms 3764 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 3 ms 3772 KB Output is correct
12 Correct 3 ms 3776 KB Output is correct
13 Correct 3 ms 3672 KB Output is correct
14 Correct 33 ms 3932 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 191 ms 17384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 191 ms 17384 KB Output is correct
5 Correct 188 ms 18512 KB Output is correct
6 Correct 218 ms 19576 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 192 ms 11848 KB Output is correct
4 Correct 183 ms 18240 KB Output is correct
5 Correct 215 ms 23484 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 141 ms 13940 KB Output is correct
8 Correct 154 ms 12640 KB Output is correct
9 Correct 163 ms 12644 KB Output is correct

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 192 ms 11848 KB Output is correct
4 Correct 183 ms 18240 KB Output is correct
5 Correct 215 ms 23484 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 141 ms 13940 KB Output is correct
8 Correct 154 ms 12640 KB Output is correct
9 Correct 163 ms 12644 KB Output is correct
10 Execution timed out 3549 ms 13916 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 4 ms 3984 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 4856 KB Output is correct
8 Correct 2 ms 3764 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 3 ms 3772 KB Output is correct
12 Correct 3 ms 3776 KB Output is correct
13 Correct 3 ms 3672 KB Output is correct
14 Correct 33 ms 3932 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 191 ms 17384 KB Output is correct
17 Correct 188 ms 18512 KB Output is correct
18 Correct 218 ms 19576 KB Output is correct
19 Correct 192 ms 11848 KB Output is correct
20 Correct 183 ms 18240 KB Output is correct
21 Correct 215 ms 23484 KB Output is correct
22 Correct 1 ms 6488 KB Output is correct
23 Correct 141 ms 13940 KB Output is correct
24 Correct 154 ms 12640 KB Output is correct
25 Correct 163 ms 12644 KB Output is correct
26 Execution timed out 3549 ms 13916 KB Time limit exceeded
27 Halted 0 ms 0 KB -