QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562256#9238. TreeZanite#13 48ms150484kbC++206.3kb2024-09-13 16:08:082024-09-13 16:08:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 16:08:11]
  • 评测
  • 测评结果:13
  • 用时:48ms
  • 内存:150484kb
  • [2024-09-13 16:08:08]
  • 提交

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.empty() && 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.empty() && 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(L == R && F[cur].slopes[i].se >= F[cur].slopes[i-1].se);
    // }
}

ll dfs_equal(ll cur) {
    ll ret = 0;
    ll sum = 0;
    for (auto nxt : child[cur]) {
        ret += dfs_equal(nxt);
        sum += L;
    }
    ret += W[cur] * abs(sum - L);
    return ret;
}

} // 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;

    if (L == R) {
        return Solve::dfs_equal(0);
    }

    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: 13
Accepted

Test #11:

score: 13
Accepted
time: 48ms
memory: 150484kb

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: 13
Accepted
time: 29ms
memory: 142392kb

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:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
127351551273446
392923435722048
219438171765380
32284843571130
53163787789189
51772420152188
31965916042830
76059397524120
296729960017452
261260002258578

result:

ok 

Test #13:

score: 13
Accepted
time: 34ms
memory: 140704kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 1 2 3 4 5 6 7 8 9 10 10 10 13 14 15 16 15 13 16 17 18 22 22 23 25 25 25 20 29 29 31 32 33 31 35 35 37 38 38 37 41 38 43 43 42 42 47 37 49 45 51 49 52 54 55 55 56 58 59 56 61 54 52 36 58 54 67 67 69 69 71 69 73 73 72 76 74 78 79 80 81 82 83 84 80 84 87 88 89 84...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
42214045518871
72831432357696
590641773997148
38954091559748
2020663055796
127157852441461
181696136766832
72411040396563
494394810335232
267249207833336

result:

ok 

Test #14:

score: 13
Accepted
time: 35ms
memory: 141144kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 1 2 3 4 5 6 7 7 7 10 11 11 13 12 15 15 15 15 17 20 21 22 23 21 16 19 23 28 29 30 31 31 31 34 23 36 37 33 23 40 41 42 42 42 43 44 40 48 44 50 51 44 53 46 55 56 47 29 59 60 60 62 62 60 65 63 67 67 69 70 71 52 73 56 75 75 63 78 78 69 81 53 83 51 85 86 87 88 89 86...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
490569818687703
477532014938406
61048882143162
83562557160256
118962344093912
133474637540285
98164499179712
19997276317472
15208959930634
62292505319353

result:

ok 

Test #15:

score: 13
Accepted
time: 33ms
memory: 140772kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 1 2 3 4 4 6 7 7 9 7 11 12 12 13 15 16 17 17 18 20 21 21 23 8 25 26 26 28 29 29 31 31 33 34 35 36 34 38 31 34 36 42 43 44 45 46 46 34 49 50 51 52 53 54 54 54 55 58 59 56 51 60 56 57 65 66 65 49 69 70 71 66 73 74 75 76 75 78 79 78 81 75 83 83 85 84 67 88 88 90 8...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
190697287624219
53603131790026
103217577508362
19182529285386
541772654508376
202493818900847
40634954006094
98609882258122
291520925855683
247847606357154

result:

ok 

Test #16:

score: 13
Accepted
time: 31ms
memory: 142056kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 1 2 3 4 5 4 5 8 6 10 10 4 8 14 15 7 17 18 18 14 20 15 23 24 24 25 27 27 29 27 30 32 23 33 26 36 37 36 32 24 33 33 43 44 45 45 46 48 48 44 21 38 53 54 54 56 56 33 59 60 61 57 37 64 65 66 65 67 67 70 71 26 73 74 73 76 77 78 78 80 81 82 82 74 85 86 85 88 89 77 91...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
7160442129933
232054458731708
111366705782284
234235829126538
252870268102869
55380890925907
160283559337139
185137158761048
16739690866131
6714786196004

result:

ok 

Test #17:

score: 13
Accepted
time: 35ms
memory: 142424kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 0 2 3 4 4 6 6 8 9 9 11 12 13 12 15 15 10 11 19 20 13 18 10 24 25 25 8 28 29 29 31 31 33 28 35 36 35 36 39 38 41 37 30 44 23 41 23 37 24 50 50 33 44 19 55 55 38 58 3 60 61 62 63 64 65 66 64 68 69 69 62 72 73 74 75 74 75 77 73 80 81 81 61 84 85 86 87 88 88 68 91...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
209059603741141
179481179940217
320133949987194
389284374280293
3450473671431
24432829075090
2164055762728
19957133648605
36369151512141
394914390055062

result:

ok 

Test #18:

score: 13
Accepted
time: 27ms
memory: 142632kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
2000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
2405489897539184
2586868257938796
2702940400172773
2629907237390536
2640721392702080
2578972752495714
2727743433629036
2570186048325034
2632300904480169
2266718396003546

result:

ok 

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #19:

score: 0
Time Limit Exceeded

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
60000
0 0 2 3 2 3 4 4 8 8 10 11 12 12 14 15 10 15 18 18 20 20 11 14 22 22 26 27 26 27 30 30 32 32 34 35 35 37 34 37 40 41 40 41 44 44 45 45 48 49 49 51 51 53 48 53 56 56 58 58 60 60 62 63 63 65 66 66 68 68 69 69 72 62 65 72 76 76 78 78 80 81 81 83 84 85 80 83 85 89 9...

output:


result:


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%