QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#325552 | #946. Magic Tree | Camillus# | 0 | 83ms | 27336kb | C++20 | 5.9kb | 2024-02-11 16:45:01 | 2024-07-04 03:23:34 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%