| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749904 |
2023-05-28T23:11:38 Z |
doowey |
Arboras (RMI20_arboras) |
C++14 |
|
224 ms |
21368 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;
vector<int> E[N];
int par[N];
ll w[N];
int n;
int sub[N];
int link[N];
int rig[N];
int tin[N];
int tout[N];
int nd[N];
int tt = -1;
ll dp0[N];
int big0[N];
ll dp1[N];
void dfs(int u){
sub[u] = 1;
dp0[u] = dp1[u] = 0ll;
big0[u] = -1;
for(auto x : E[u]){
dfs(x);
if(dp0[x] + w[x] > dp0[u]){
big0[u] = x;
dp1[u] = dp0[u];
dp0[u] = dp0[x] + w[x];
}
else if(dp0[x] + w[x] > dp1[u]){
dp1[u] = dp0[x] + w[x];
}
sub[u] += sub[x];
}
}
void dfs1(int u){
tt ++ ;
tin[u] = tt;
nd[tin[u]] = u;
if(link[u] == -1) link[u] = u;
rig[link[u]] = tin[u];
int nx = -1;
for(auto x : E[u]){
if(nx == -1 || sub[x] > sub[nx]){
nx = x;
}
}
if(nx != -1){
link[nx]=link[u];
}
if(nx != -1){
dfs1(nx);
}
for(auto x : E[u]){
if(x != nx)
dfs1(x);
}
tout[u] = tt;
}
struct Node{
ll dp;
int id;
};
Node T[N * 4 + 24];
ll sum = 0;
void inc(ll y){
y %= MOD;
sum += y;
if(sum < 0) sum += MOD;
else if(sum >= MOD) sum -= MOD;
}
void build(int node, int cl, int cr){
if(cl == cr){
if(big0[nd[cl]] == -1 || link[big0[nd[cl]]] != link[nd[cl]])
T[node].id = cl;
else
T[node].id = -1;
T[node].dp = dp0[nd[cl]];
inc(dp0[nd[cl]] + dp1[nd[cl]]);
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].dp = 0ll;
T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}
int query_id(int node, int cl, int cr, int tl, int tr){
if(cr < tl || cl > tr) return -1;
if(cl >= tl && cr <= tr){
return T[node].id;
}
int mid = (cl + cr) / 2;
return max(query_id(node * 2, cl, mid, tl, tr), query_id(node * 2 + 1, mid + 1, cr, tl, tr));
}
void set_id(int node, int cl, int cr, int id, int p){
if(cl == cr){
T[node].id = p;
return;
}
int mid = (cl + cr) / 2;
if(mid >= id)
set_id(node * 2, cl, mid, id, p);
else
set_id(node * 2 + 1, mid + 1, cr, id, p);
T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}
void push(int node, int cl, int cr){
if(cl != cr){
T[node * 2].dp += T[node].dp;
T[node * 2 + 1].dp += T[node].dp;
T[node].dp = 0;
}
}
void add_dp(int node, int cl, int cr, int tl, int tr, ll W){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
inc((cr - cl + 1) * 1ll * W);
T[node].dp += W;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
add_dp(node * 2, cl, mid, tl, tr, W);
add_dp(node * 2 + 1, mid + 1, cr, tl, tr, W);
}
ll ask_dp(int node, int cl, int cr, int idx){
push(node, cl, cr);
if(cl == cr){
return T[node].dp;
}
int mid = (cl + cr) / 2;
if(mid >= idx)
return ask_dp(node * 2, cl, mid, idx);
else
return ask_dp(node * 2 + 1, mid + 1, cr, idx);
}
ll get_dp(int node){
return ask_dp(1, 0, n - 1, tin[node]);
}
ll add;
void check_up(int &v){
ll f = get_dp(v) + w[v];
ll par_dp = get_dp(par[v]);
if(big0[par[v]] == v){
add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
v = par[v];
}
else{
if(f > par_dp){
add = f - par_dp;
add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
if(link[par[v]] == link[v]){
set_id(1, 0, n - 1, tin[par[v]], -1);
}
else{
set_id(1, 0, n - 1, tin[par[v]], tin[par[v]]);
}
inc(par_dp-dp1[par[v]]);
dp1[par[v]] = par_dp;
big0[par[v]] = v;
v=par[v];
}
else if(f > dp1[par[v]]){
inc(f-dp1[par[v]]);
dp1[par[v]] = f;
v=0;
}
else{
v = 0;
}
}
}
ll n0[N];
ll n1[N];
void dfs2(int u){
n0[u] = n1[u] = 0ll;
for(auto x : E[u]){
dfs2(x);
if(n0[x] + w[x] > n0[u]){
n1[u] = n0[u];
n0[u] = n0[x] + w[x];
}
else if(n0[x] + w[x] > n1[u]){
n1[u] = n0[x] + w[x];
}
}
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
cin >> n;
for(int i = 1; i < n; i ++ ){
cin >> par[i];
E[par[i]].push_back(i);
}
for(int i = 1; i < n; i ++ ){
cin >> w[i];
}
for(int i = 0 ; i < n; i ++ ){
link[i] = -1;
}
dfs(0);
dfs1(0);
build(1, 0, n - 1);
dfs2(0);
cout << sum << "\n";
int q;
cin >> q;
int v;
int g;
int i0, i1;
for(int iq = 1; iq <= q; iq ++ ){
cin >> v >> add;
// implement ze walk up
w[v] += add;
while(v > 0){
if(v == link[v]){
check_up(v);
}
else{
g = query_id(1, 0, n - 1, tin[link[v]], tin[v] - 1);
if(g == -1){
add_dp(1, 0, n - 1, tin[link[v]], tin[v] - 1, add);
v = link[v];
}
else{
add_dp(1, 0, n - 1, g + 1, tin[v] - 1, add);
v=nd[g + 1];
check_up(v);
}
}
}
cout << sum << "\n";
}
return 0;
}
Compilation message
arboras.cpp: In function 'int main()':
arboras.cpp:245:9: warning: unused variable 'i0' [-Wunused-variable]
245 | int i0, i1;
| ^~
arboras.cpp:245:13: warning: unused variable 'i1' [-Wunused-variable]
245 | int i0, i1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
16368 KB |
Output is correct |
| 2 |
Correct |
82 ms |
15172 KB |
Output is correct |
| 3 |
Correct |
91 ms |
15324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
18172 KB |
Output is correct |
| 2 |
Correct |
100 ms |
20300 KB |
Output is correct |
| 3 |
Correct |
86 ms |
16244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 4 |
Correct |
224 ms |
16368 KB |
Output is correct |
| 5 |
Correct |
82 ms |
15172 KB |
Output is correct |
| 6 |
Correct |
91 ms |
15324 KB |
Output is correct |
| 7 |
Correct |
118 ms |
18172 KB |
Output is correct |
| 8 |
Correct |
100 ms |
20300 KB |
Output is correct |
| 9 |
Correct |
86 ms |
16244 KB |
Output is correct |
| 10 |
Correct |
147 ms |
18252 KB |
Output is correct |
| 11 |
Correct |
96 ms |
20300 KB |
Output is correct |
| 12 |
Correct |
105 ms |
16340 KB |
Output is correct |
| 13 |
Correct |
105 ms |
20616 KB |
Output is correct |
| 14 |
Correct |
96 ms |
21368 KB |
Output is correct |
