QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#325552#946. Magic TreeCamillus#0 83ms27336kbC++205.9kb2024-02-11 16:45:012024-07-04 03:23:34

Judging History

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

  • [2024-07-04 03:23:34]
  • 评测
  • 测评结果：0
  • 用时：83ms
  • 内存：27336kb
查看
  • [2024-02-11 16:45:01]
  • 提交

answer

/// @author Camillus <3
#include "bits/stdc++.h"

using ll = long long;
using namespace std;

int p[100500];
vector<int> g[100500];
int h[100500];

int sz[100500];
void dfs_sz(int u) {
    sz[u] = 1;
    for (int& v : g[u]) {
        dfs_sz(v);
        sz[u] += sz[v];
    }
}

void dfs_h(int u) {
    if (!g[u].empty()) {
        for (int v : g[u]) {
            h[v] = v;
        }
        h[g[u].front()] = h[u];
    }

    for (int v : g[u]) {
        dfs_h(v);
    }
}

pair<int, int> f[100500];

struct segment_tree {
    segment_tree() = default;

    static constexpr ll NOP = LLONG_MAX;

    struct node {
        ll max = 0;
        ll add = 0;
        ll op = NOP;
    };

    vector<node> tree;
    int n = 0;

    segment_tree(int m) {
        n = 1;
        while (n < m) {
            n *= 2;
        }
        tree.resize(n * 2 - 1);
    }

//    void apply_add(int x, ll v);
//    void apply_op(int x, ll v);

    void push(int x) {
        if (tree[x].add != 0) {
            apply_add(x * 2 + 1, tree[x].add);
            apply_add(x * 2 + 2, tree[x].add);
            tree[x].add = 0;
        }
        if (tree[x].op != NOP) {
            apply_op(x, tree[x].op);
            apply_op(x, tree[x].op);
            tree[x].op = NOP;
        }
    }

    void apply_add(int x, ll v) {
        if (tree[x].op != NOP) {
            push(x);
        }
        tree[x].max += v;
        tree[x].add += v;
    }

    void apply_op(int x, ll v) {
        tree[x].max = v;
        tree[x].add = 0;
        if (x * 2 + 2 < 4 * n) {
            tree[x].op = v;
        }
    }

    void pull(int x) {
        tree[x].max = max(tree[x * 2 + 1].max, tree[x * 2 + 2].max);
    }

    void op(int l, int r, ll v, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = n;
        }

        if (l <= lx && rx <= r) {
            apply_op(x, v);
            return;
        }

        if (l >= rx || lx >= r) {
            return;
        }

        push(x);

        op(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
        op(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);

        pull(x);
    }

    void add(int l, int r, ll v, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = n;
        }

        if (l <= lx && rx <= r) {
            apply_add(x, v);
            return;
        }

        if (l >= rx || lx >= r) {
            return;
        }

        push(x);

        add(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
        add(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);

        pull(x);
    }

    ll get(int i, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = n;
        }

        if (rx - lx == 1) {
            return tree[x].max;
        }

        push(x);

        if (i < (lx + rx) / 2) {
            return get(i, x * 2 + 1, lx, (lx + rx) / 2);
        } else {
            return get(i, x * 2 + 2, (lx + rx) / 2, rx);
        }
    }

    int lower_bound(ll v, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1) {
            rx = n;
        }

        if (rx - lx == 1) {
            return lx;
        }

        push(x);

        if (tree[x * 2 + 1].max >= v) {
            return lower_bound(v, x * 2 + 1, lx, (lx + rx) / 2);
        } else {
            return lower_bound(v, x * 2 + 2, (lx + rx) / 2, rx);
        }
    }
};

struct ds {
    vector<int> keys;
    ds() {}

    void add_key(int day) {
        keys.push_back(day);
    }

    int n;
    segment_tree st;

    void build() {
        ranges::sort(keys);
        keys.erase(unique(keys.begin(), keys.end()), keys.end());
        n = (int)keys.size();
        st = segment_tree(n);
    }

    int lower_bound(int key) {
        auto i = ranges::lower_bound(keys, key) - keys.begin();
        return i;
    }

    void add(int l, int r, ll v) {
        st.add(l, r + 1, v);
    }

    void op(int l, int r, ll v) {
        st.op(l, r + 1, v);
    }

    ll get(int i) {
        return st.get(i);
    }
};

ds DS[100500];
void make_ds(int n) {
    for (int u = 1; u <= n; u++) {
        if (h[u] == u) {
            auto dfs = [&r=u](auto &&dfs, int u) -> void {
                if (f[u].first) {
                    DS[r].add_key(f[u].first);
                }
                for (int v : g[u]) {
                    dfs(dfs, v);
                }
            };
            dfs(dfs, u);
            DS[u].build();
        }
    }
}

void dfs(int u) {
    for (int v : g[u]) {
        dfs(v);

        if (v != g[u].front()) {
            for (int i = 0; i < DS[v].n; i++) {
                int L = DS[v].keys[i];
                int R = 2'000'000'000;
                if (i + 1 != DS[v].n) {
                    R = DS[v].keys[i + 1];
                }

                ll D = DS[v].get(i);

                L = DS[h[u]].lower_bound(L);
                R = DS[h[u]].lower_bound(R);

                DS[h[u]].add(L, R - 1, D);
            }
        }
    }

    if (f[u].first != 0) {
        int i = DS[h[u]].lower_bound(f[u].first);
        ll value = DS[h[u]].get(i) + f[u].second;

        if (DS[h[u]].get(DS[h[u]].n - 1) <= value) {
            DS[h[u]].op(i, DS[h[u]].n - 1, value);
        } else {
            int j = DS[h[u]].st.lower_bound(value);
            DS[h[u]].op(i, j - 1, value);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    h[1] = 1;

    int n, m, k;
    cin >> n >> m >> k;

    for (int u = 2; u <= n; u++) {
        cin >> p[u];
        g[p[u]].push_back(u);
    }

    for (int i = 0; i < m; i++) {
        int u, d, w;
        cin >> u >> d >> w;

        f[u] = {d, w};
    }

    dfs_sz(1);
    dfs_h(1);
    make_ds(n);
    dfs(1);

    cout << DS[1].get(DS[1].n - 1) << '\n';
    return 0;
}
源文件, 语言: C++20

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11256kb

input:

10 9 10
1
1
2
2
3
1
3
8
3
5 4 1
9 4 1
6 8 1
3 1 1
4 9 1
10 1 1
2 6 1
8 7 1
7 9 1

output:

6

result:

wrong answer expected '7', found '6'

Subtask #2:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 83ms
memory: 27336kb

input:

100000 25000 100000
1
1
2
1
2
1
5
8
8
2
5
2
2
3
1
2
11
10
18
2
9
9
9
8
1
19
18
22
20
17
20
13
30
5
9
8
13
2
19
26
14
31
23
22
2
21
8
1
22
9
50
19
49
42
47
19
21
57
9
52
41
39
10
14
60
56
34
17
18
22
53
5
34
64
29
72
33
11
9
67
58
10
58
70
57
26
65
10
15
64
67
20
26
13
51
81
11
78
40
53
70
33
34
92
7...

output:

11337785728919

result:

wrong answer expected '12471468294549', found '11337785728919'

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 3ms
memory: 11628kb

input:

1000 500 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
9...

output:

1

result:

wrong answer expected '3', found '1'

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 57ms
memory: 21560kb

input:

100000 90000 2
1
1
3
2
1
2
1
5
1
8
11
9
1
8
12
7
1
2
7
6
12
9
16
18
13
10
23
27
26
17
23
10
24
11
21
13
30
1
11
6
13
8
30
15
17
34
39
41
32
29
27
17
21
12
26
33
10
50
29
17
46
33
21
28
47
26
3
67
38
5
10
45
61
70
59
17
46
40
20
58
67
68
15
62
71
71
57
32
81
18
66
7
14
51
67
92
86
38
88
60
45
54
5
59...

output:

31233391721978

result:

wrong answer expected '38521956905095', found '31233391721978'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 8ms
memory: 15120kb

input:

20000 800 60000
1
1
1
2
3
1
7
8
6
1
7
6
1
7
14
16
11
13
14
3
11
11
4
2
5
24
20
24
16
30
15
3
24
31
12
7
2
29
14
25
39
23
16
33
32
33
34
9
13
37
33
23
15
21
28
39
51
19
6
50
54
55
8
40
3
7
34
19
28
15
61
18
22
28
38
15
47
37
42
73
38
61
10
7
30
58
41
43
69
89
62
84
30
68
92
84
43
59
44
75
8
100
83
18...

output:

362561759066

result:

wrong answer expected '386917987664', found '362561759066'

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-29 12:30:18 | 开源项目