QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498201 | #9165. Petrol stations | Qwerty1232 | 0 | 0ms | 3568kb | C++23 | 8.9kb | 2024-07-30 04:31:17 | 2024-07-30 04:31:17 |
answer
#include <bits/stdc++.h>
// #define int int64_t
int K;
struct Shit {
int64_t tm;
int cnt, prf;
bool operator<(const Shit& other) const {
return tm < other.tm;
}
};
struct Cum {
int64_t dlt;
int sh;
std::vector<Shit> vec;
bool operator<(const Cum& other) const {
return false;
}
};
using Fuck = std::vector<Cum>;
// using Fuck2 = std::pair<int64_t, Fuck>;
int cum_size(const Cum& c) {
return c.vec.size() - c.sh;
}
void cum_push(Cum& a) {
for (int i = a.sh; i < a.vec.size(); i++) {
a.vec[i].tm += a.dlt;
}
}
Cum cum_merge(Cum& a, Cum& b) {
Cum res(0, 0, {});
cum_push(a);
cum_push(b);
res.vec.resize(cum_size(a) + cum_size(b));
std::merge(a.vec.begin() + a.sh, a.vec.end(),
b.vec.begin() + b.sh, b.vec.end(),
res.vec.begin());
for (int i = 0, s = 0; i < res.vec.size(); i++) {
res.vec[i].prf = (s += res.vec[i].cnt);
}
a.dlt = 0, a.sh = 0, a.vec.clear();
b.dlt = 0, b.sh = 0, b.vec.clear();
return res;
}
// merges to a
void fuck_merge(Fuck& a, Fuck& b) {
a.resize(std::max(a.size(), b.size()) + 1);
Cum carry{0, 0, {}};
for (int i = 0; i < a.size(); i++) {
if (cum_size(carry)) {
if (cum_size(a[i])) {
carry = cum_merge(carry, a[i]);
} else {
a[i] = std::move(carry);
}
}
if (i < b.size() && cum_size(b[i])) {
if (cum_size(a[i])) {
carry = cum_merge(a[i], b[i]);
} else {
a[i] = std::move(b[i]);
}
}
}
assert(cum_size(carry) == 0);
while (a.size() && cum_size(a.back()) == 0) {
a.pop_back();
}
b.clear();
}
__attribute__((optimize("O3"), target("avx2"))) std::pair<int, int> cum_fisting(Cum& c, int w) {
c.dlt -= w;
int dlt = 0;
int sum = 0;
int it = std::lower_bound(c.vec.begin() + c.sh, c.vec.end(), Shit{-c.dlt}) - c.vec.begin();
// while (cum_size(c) && c.vec[c.sh].tm + c.dlt < 0) {
sum = c.vec[it - 1].prf - (c.sh == 0 ? 0 : c.vec[c.sh - 1].prf);
// for (int i = c.sh; i < it; i++) {
// sum += c.vec[i].cnt;
// }
dlt = it - c.sh;
c.sh = it;
if (dlt) {
c.vec.push_back({(K - w) - c.dlt, sum});
c.vec.back().prf = c.vec.back().cnt + (c.vec.size() == 1 ? 0 : c.vec.rbegin()[1].prf);
}
return {dlt, sum};
}
int fuck_fisting(Fuck& f, int w) {
int sum = 0;
for (auto& cum : f) {
auto [dt, sm] = cum_fisting(cum, w);
sum += sm;
}
return sum;
}
void cum_reverse_fisting(Cum& c, int w, int ftg) {
c.dlt += w;
if (ftg) {
c.sh -= ftg;
c.vec.pop_back();
}
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n >> K;
std::vector<std::vector<std::pair<int, int>>> gr(n);
std::vector<std::vector<int64_t>> dp(n);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
std::cin >> u >> v >> w;
gr[u].push_back({v, w}), gr[v].push_back({u, w});
}
for (int i = 0; i < n; i++) {
dp[i].resize(gr[i].size());
}
std::vector<int> fising_sz(n), fisting_depth(n);
{
auto dfs = [&](auto dfs, int v, int f) -> void {
fising_sz[v] = 1;
for (auto [t, w] : gr[v]) {
if (t != f) {
fisting_depth[t] = fisting_depth[v] + 1;
dfs(dfs, t, v);
fising_sz[v] += fising_sz[t];
}
}
};
dfs(dfs, 0, -1);
}
auto get_sb_sz = [&](int u, int v) {
if (fisting_depth[u] < fisting_depth[v]) {
return fising_sz[v];
}
return n - fising_sz[u];
};
// for (int i = 0; i < n; i++) {
// auto dfs = [&](auto dfs, int v, int fr) -> Fuck {
// Fuck f;
// f.push_back(Cum{0, 0, {Shit{K, 1}}});
// for (int ti = 0; ti < gr[v].size(); ti++) {
// auto [t, w] = gr[v][ti];
// if (t == fr) {
// continue;
// }
// auto f2 = dfs(dfs, t, v);
// int sum = fuck_fisting(f2, w);
// dp[v][ti] = sum;
// fuck_merge(f, f2);
// }
// return f;
// };
// dfs(dfs, i, -1);
// }
std::vector<int> sz(n), used(n, 0);
auto find = [&](int v) {
auto dfs = [&](auto dfs, int v, int f) -> void {
sz[v] = 1;
for (auto [t, w] : gr[v]) {
if (t != f && !used[t]) {
dfs(dfs, t, v);
sz[v] += sz[t];
}
}
};
dfs(dfs, v, -1);
int f = -1;
int s = sz[v];
while (true) {
auto it = std::find_if(gr[v].begin(), gr[v].end(), [&](auto p) { return p.first != f && !used[p.first] && sz[p.first] > s / 2; });
if (it == gr[v].end()) {
break;
} else {
f = v;
v = it->first;
}
}
return v;
};
std::vector<int64_t> ans(n, 0);
auto build = [&](auto build, int v) -> void {
v = find(v);
auto dfs = [&](auto dfs, int v, int fr, int cum_left, int sm = 0) -> Fuck {
sz[v] = 1;
Fuck f;
f.push_back(Cum{0, 0, {Shit{K, 1}}});
for (int ti = 0; ti < gr[v].size(); ti++) {
auto [t, w] = gr[v][ti];
if (t == fr) {
dp[v][ti] += sm;
continue;
}
if (used[t]) {
continue;
}
int sum = int(cum_left - w < 0);
// dp[v][ti] += sum;
// ans[v] += sum;
auto f2 = dfs(dfs, t, v, cum_left - w < 0 ? K - w : cum_left - w, sum);
sz[v] += sz[t];
fuck_fisting(f2, w);
fuck_merge(f, f2);
}
return f;
};
// struct Cmp {
// template <typename T>
// bool operator()(const T& a, const T& b) const {
// return a.first < b.first;
// }
// };
std::priority_queue<std::pair<std::pair<int, std::vector<int>>, Cum>> heap;
for (int ti = 0, xx = 0; ti < gr[v].size(); ti++) {
auto [t, w] = gr[v][ti];
if (used[t]) {
continue;
}
Fuck f;
f.push_back(Cum{0, 0, {}});
xx = 1;
auto f2 = dfs(dfs, t, v, K - w);
int sum = fuck_fisting(f2, w);
dp[v][ti] += sum;
fuck_merge(f, f2);
Cum c(0, 0, {});
for (auto& c2 : f) {
c = cum_merge(c, c2);
}
heap.push({{-sz[t], {ti}}, std::move(c)});
}
while (heap.size() > 1) {
auto [p1, c1] = heap.top();
heap.pop();
auto [p2, c2] = heap.top();
heap.pop();
auto [sz1, ti1] = p1;
auto [sz2, ti2] = p2;
auto dfs = [&](auto dfs, int v, int f, int fw, int f_id, Cum& c) -> void {
auto [fisting, sum] = cum_fisting(c, fw);
// dp[f][f_id] += sum;
for (int ti = 0; ti < gr[v].size(); ti++) {
auto [t, w] = gr[v][ti];
if (t == f) {
dp[v][ti] += sum;
continue;
}
if (used[t]) {
continue;
}
dfs(dfs, t, v, w, ti, c);
}
cum_reverse_fisting(c, fw, fisting);
};
for (auto ti : ti1) {
dfs(dfs, gr[v][ti].first, v, gr[v][ti].second, ti, c2);
}
for (auto ti : ti2) {
dfs(dfs, gr[v][ti].first, v, gr[v][ti].second, ti, c1);
}
Cum c = cum_merge(c1, c2);
ti1.insert(ti1.end(), ti2.begin(), ti2.end());
heap.push({{sz1 + sz2, ti1}, std::move(c)});
}
used[v] = true;
for (auto [t, w] : gr[v]) {
if (!used[t]) {
build(build, t);
}
}
};
build(build, 0);
for (int v = 0; v < n; v++) {
for (int ti = 0; ti < gr[v].size(); ti++) {
auto [t, w] = gr[v][ti];
ans[t] += int64_t(dp[v][ti]) * get_sb_sz(t, v);
}
}
for (int i = 0; i < n; i++) {
std::cout << ans[i] << "\n\n"[i == n - 1];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
750 918 159 63 18 573 310 105 135 400 57 618 27 113 41 265 24 99 576 61 242 85 109 490 88 0 626 721 0 407 446 0 78 644 124 346 198 17 541 504 147 543 423 24 302 450 25 397 344 80 129 607 76 474 59 140 30 10 29 375 260 1 404 81 0 658 695 153 450 100 92 532 249 10 597 151 133 739 714 0 212 345 85 558 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #13:
score: 8
Accepted
time: 0ms
memory: 3568kb
input:
2 1 0 1 1
output:
0 0
result:
ok 2 lines
Test #14:
score: 0
Runtime Error
input:
70000 1 50913 18377 1 33894 11911 1 61940 7863 1 61602 33470 1 26341 35575 1 30813 50301 1 2994 67214 1 38527 61714 1 37381 3396 1 43274 14867 1 59352 12066 1 68877 40750 1 44756 43671 1 57921 17977 1 10879 47719 1 26878 13556 1 27329 23697 1 45109 11513 1 21307 12312 1 27202 27807 1 7250 14810 1 27...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #17:
score: 0
Runtime Error
input:
69973 4 44281 27162 1 15299 61302 1 19250 66379 1 45970 65938 1 23683 4445 2 62232 40589 1 37028 58991 2 58769 32024 0 41860 69672 2 14687 10058 2 7874 6780 2 60579 37047 2 739 4096 2 53137 22114 2 35060 21464 0 42597 11591 2 68051 23473 2 61458 35690 2 38719 6601 2 57406 26025 1 38192 41521 0 47941...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%