# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
646596 |
2022-09-30T09:26:06 Z |
Vanilla |
Arboras (RMI20_arboras) |
C++17 |
|
221 ms |
55608 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 mod = 1e9 + 7;
const int maxn = 1e5 + 2;
int64 dp[maxn], down[maxn];
map <pair <int, int>, int64> c;
int p[maxn];
vector <int> ad [maxn];
multiset <int64> ms[maxn];
int n;
void upd (int u) {
vector <int64> d;
down[u] = 0;
dp[u] = 0;
for (int v: ad[u]) {
down[u] = max(down[u], down[v] + c[{u,v}]);
d.push_back(down[v] + c[{u,v}]);
ms[u].insert(down[v] + c[{u, v}]);
}
sort(d.rbegin(), d.rend());
for (int i = 0; i < min((int) d.size(), 2); i++) dp[u]+=d[i];
}
void dfs (int u) {
for (int v: ad[u]) {
dfs(v);
}
upd(u);
}
int main() {
cin >> n;
for (int i = 1; i <= n - 1; i++){
int x;
cin >> x;
ad[x].push_back(i);
p[i] = x;
}
for (int i = 1; i <= n - 1; i++){
int x;
cin >> x;
c[{p[i], i}] = x;
}
int q;
cin >> q;
dfs(0);
p[0] = -1;
int64 rs = 0;
for (int i = 0; i < n; i++){
ms[i].insert(0);
rs = (rs + dp[i]) % mod;
}
cout << rs << "\n";
while (q--) {
int64 x,y;
cin >> x >> y;
int u = x;
while (u) {
ms[p[u]].erase(ms[p[u]].find(*--ms[u].end() + c[{p[u], u}]));;
rs = (rs - dp[p[u]] + mod) % mod;
dp[p[u]] = 0;
u = p[u];
}
c[{p[x], x}]+=y;
u = x;
while (u) {
ms[p[u]].insert(*--ms[u].end() + c[{p[u], u}]);
if (ms[p[u]].size() >= 1) dp[p[u]] += *--ms[p[u]].end();
if (ms[p[u]].size() >= 2) dp[p[u]] += *----ms[p[u]].end();
rs = (rs + dp[p[u]] + mod) % mod;
u = p[u];
}
cout << rs << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
15064 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
221 ms |
53732 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
154 ms |
55608 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
15064 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |