QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562238 | #9238. Tree | Zanite# | 0 | 56ms | 149176kb | C++20 | 6.0kb | 2024-09-13 15:59:00 | 2024-09-13 15:59:01 |
Judging History
answer
#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define fi first
#define se second
#define All(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n"
template<typename T> bool chmax(T &u, T v) { if (u < v) { u = v; return true; } return false; }
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U> &v) {
return os << "(" << v.fi << ", " << v.se << ")";
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T> &v) {
os << "["; bool _first = true;
for (auto i : v) { if (!_first) { os << ", "; } os << i; _first = false; }
return os << "]";
}
template<typename T>
ostream& operator<<(ostream& os, const deque<T> &v) {
os << "["; bool _first = true;
for (auto i : v) { if (!_first) { os << ", "; } os << i; _first = false; }
return os << "]";
}
namespace Solve {
struct Func {
ll start;
deque<pll> slopes;
Func() : start(0), slopes(0) {}
Func(ll L, ll R, ll W) {
start = L*W;
slopes = {{R - L, W}};
}
ll getMinimum() {
ll ret = start, run = start;
for (int i = 0; i < (int)slopes.size(); i++) {
run += slopes[i].fi * slopes[i].se;
ret = min(ret, run);
}
return ret;
}
static Func merge(Func a, Func b, ll L, ll R, ll W) {
Func ret;
ret.start = a.start + b.start;
ret.slopes = {};
ll cx = 2ll * L;
while (!a.slopes.empty() || !b.slopes.empty()) {
// cerr << a.slopes.size() << " " << b.slopes.size() << "\n";
if (!a.slopes.empty() && !b.slopes.empty()) {
if (a.slopes.front().se < b.slopes.front().se) {
ret.slopes.push_back(a.slopes.front());
a.slopes.pop_front();
} else {
ret.slopes.push_back(b.slopes.front());
b.slopes.pop_front();
}
} else if (!a.slopes.empty()) {
ret.slopes.push_back(a.slopes.front());
a.slopes.pop_front();
} else {
ret.slopes.push_back(b.slopes.front());
b.slopes.pop_front();
}
}
// pad front
while (!ret.slopes.empty() && ret.slopes.front().se < -W) {
ret.start += ret.slopes.front().fi * ret.slopes.front().se;
cx += ret.slopes.front().fi;
ret.slopes.pop_front();
}
ret.slopes.push_front({cx - L, -W});
ret.start -= ret.slopes.front().fi * ret.slopes.front().se;
// pop back
ll sum = 0;
for (auto [len, slope] : ret.slopes) sum += len;
while (sum > R-L) {
ll tk = sum - (R-L);
// cerr << "tk " << tk << "\n";
if (ret.slopes.back().fi <= tk) {
sum -= ret.slopes.back().fi;
if (ret.slopes.size() > 1) {
ret.slopes.pop_back();
} else {
ret.slopes.back().fi = 0;
}
} else {
ret.slopes.back().fi -= tk;
break;
}
}
// cerr << ret.slopes << "\n";
return ret;
}
static Func clip(Func a, ll L, ll R, ll W) {
// pad front
ll cx = L;
while (a.slopes.front().se < -W) {
a.start += a.slopes.front().fi * a.slopes.front().se;
cx += a.slopes.front().fi;
a.slopes.pop_front();
}
if (cx > L) {
a.slopes.push_front({cx - L, -W});
a.start -= a.slopes.front().fi * a.slopes.front().se;
}
// pad back
ll rem = 0;
while (a.slopes.back().se > W) {
rem += a.slopes.back().fi;
a.slopes.pop_back();
}
if (rem > 0) a.slopes.push_back({rem, W});
return a;
}
};
const int maxN = 200'023;
int N;
vector<int> child[maxN];
ll W[maxN];
Func F[maxN];
ll L, R;
void dfs(int cur) {
if (child[cur].empty()) {
F[cur] = Func(L, R, W[cur]);
return;
}
for (auto nxt : child[cur]) dfs(nxt);
if (child[cur].size() == 1) {
F[cur] = Func::clip(F[child[cur][0]], L, R, W[cur]);
} else {
F[cur] = Func::merge(F[child[cur][0]], F[child[cur][1]], L, R, W[cur]);
for (int i = 2; i < (int)child[cur].size(); i++) {
F[cur] = Func::merge(F[cur], F[child[cur][i]], L, R, W[cur]);
}
}
for (int i = 1; i < (int)F[cur].slopes.size(); i++) {
assert(F[cur].slopes[i].se >= F[cur].slopes[i-1].se);
}
}
} // namespace Solve
void init(vector<int> P, vector<int> W) {
Solve::N = P.size();
for (int i = 1; i < Solve::N; i++) Solve::child[P[i]].push_back(i);
for (int i = 0; i < Solve::N; i++) Solve::W[i] = W[i];
}
ll query(int L, int R) {
Solve::L = L, Solve::R = R;
Solve::dfs(0);
// for (int i = 0; i < Solve::N; i++) {
// cout << i << ":\n";
// cout << Solve::F[i].start << "\n";
// cout << Solve::F[i].slopes << "\n\n";
// }
return Solve::F[0].getMinimum();
}
#ifdef Zanite
#include "tree.h"
#include <cassert>
#include <cstdio>
int main() {
int N;
assert(1 == scanf("%d", &N));
vector<int> P(N);
P[0] = -1;
for (int i = 1; i < N; i++)
assert(1 == scanf("%d", &P[i]));
vector<int> W(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &W[i]));
int Q;
assert(1 == scanf("%d", &Q));
vector<int> L(Q), R(Q);
for (int j = 0; j < Q; j++)
assert(2 == scanf("%d%d", &L[j], &R[j]));
fclose(stdin);
init(P, W);
vector<long long> A(Q);
for (int j = 0; j < Q; j++)
A[j] = query(L[j], R[j]);
for (int j = 0; j < Q; j++)
printf("%lld\n", A[j]);
fclose(stdout);
return 0;
}
#endif
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 2 2 4 5 4 5 8 9 10 9 8 10 14 15 14 15 18 19 20 21 18 22 21 24 24 27 22 27 30 31 31 33 30 19 20 33 38 38 40 41 41 43 44 43 44 47 48 49 50 49 50 53 54 53 48 54 58 58 60 60 62 62 64 64 66 66 67 67 70 71 72 71 72 75 70 75 78 78 80 81 80 81 84 85 86 86 88 89 90...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #11:
score: 13
Accepted
time: 56ms
memory: 149176kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 0 1 1 4 4 6 7 6 7 10 10 12 12 14 15 14 15 18 19 19 21 18 21 24 24 26 27 26 27 30 30 32 32 34 34 36 37 38 39 39 41 37 38 36 41 46 47 48 47 48 51 51 53 54 54 56 56 58 58 60 61 61 63 64 64 66 67 66 67 70 71 72 72 74 75 76 76 75 74 70 77 63 60 77 85 85 87 87 89 89...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 175909322571 633257447922 815909942751 39651169609 1036267874610 610572524261 164360385196 32373687020 128373030516 267765616314
result:
ok
Test #12:
score: 0
Runtime Error
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 14 18 16 20 21 22 22 20 25 20 27 28 28 30 29 32 29 34 29 35 29 30 26 40 41 42 41 44 45 46 47 48 49 48 49 49 53 54 54 48 52 55 59 59 61 61 50 64 65 66 64 66 69 70 51 72 72 73 75 76 77 77 78 74 81 82 73 84 74 76 87 87 89 90...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 2 2 6 6 7 7 10 11 11 13 14 13 14 17 10 17 20 21 22 22 23 21 20 23 28 29 28 29 32 33 34 32 33 34 38 39 39 40 42 42 44 45 46 47 48 45 46 48 52 53 53 54 56 56 58 58 60 61 62 63 63 65 61 66 62 66 70 71 71 72 72 75 60 65 75 79 52 44 70 47 40 54 79 87 87 89 ...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #47:
score: 0
Time Limit Exceeded
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 4 5 5 7 7 9 9 11 12 13 13 11 14 12 14 19 20 19 20 23 24 25 26 26 28 28 30 31 32 33 33 35 35 30 32 31 37 41 42 43 24 44 46 46 48 49 50 51 51 53 54 55 55 56 56 48 50 54 44 59 49 25 59 67 68 67 68 71 71 72 72 75 76 76 78 79 80 37 80 83 83 85 86 85 79 41 8...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%