oj.uz

Submission #943601

# Submission time Handle Problem Language Result Execution time Memory
943601 2024-03-11T16:11:33 Z vjudge1 Arboras (RMI20_arboras) C++17
100 / 100
 256 ms 36692 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,p[100001],d[100001],q,h[100001],tin[100001],tout[100001],pos[100001],nxt[100001],t,res,lazy[400001];
vector <int> ke[100001];
vector <pair <int, int>> ke2[100001];
pair <int, int> mx[100001][2],st[400001];
void dfs(int u){
    nxt[u]=u;
    tin[u]=++t;
    pos[t]=u;
    mx[u][0]=mx[u][1]={d[u],u};
    for (int v:ke[u]){
        h[v]=h[u]+1;
        d[v]+=d[u];
        dfs(v);
        ke2[u].push_back({tout[v],v});
        if (mx[v][0]>mx[u][0]){
            mx[u][1]=mx[u][0];
            mx[u][0]=mx[v][0];
        }
        else
            mx[u][1]=max(mx[u][1],mx[v][0]);
    }
    res=(res+mx[u][0].first+mx[u][1].first-d[u]*2)%mod;
    nxt[mx[u][0].second]=u;
    tout[u]=t;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={d[pos[l]],pos[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=max(st[node<<1],st[node<<1|1]);
}
void recompute(int node, int val){
    st[node].first+=val;
    lazy[node]+=val;
}
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    recompute(node<<1,lazy[node]);
    recompute(node<<1|1,lazy[node]);
    lazy[node]=0;
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        recompute(node,val);
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=max(st[node<<1],st[node<<1|1]);
}
pair <int, int> get(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r||u>v)
        return {0,0};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return max(get(node<<1,l,mid,u,v),get(node<<1|1,mid+1,r,u,v));
}
void jump(int &u, int v, int val){
    res=(res+(h[u]-h[v])*val%mod)%mod;
    u=nxt[v];
}
void walk(int u, int val){
    int tmp=u;
    auto [cur,V]=get(1,1,n,tin[u],tout[u]);
    jump(u,nxt[V],val);
    cur+=val;
    while (u){
        int w=p[u];
        auto [mx,v]=get(1,1,n,tin[w],tout[w]);
        int pos=lower_bound(ke2[w].begin(),ke2[w].end(),make_pair(tout[v],0LL))-ke2[w].begin();
        int c=ke2[w][pos].second;
        auto [mx2,v2]=max(get(1,1,n,tin[w],tin[c]-1),get(1,1,n,tout[c]+1,tout[w]));
        if (make_pair(cur,V)>make_pair(mx,v)){
            nxt[V]=nxt[v];
            nxt[v]=c;
            jump(u,nxt[V],cur-mx);
            res=(res+mx-mx2)%mod;
        }
        else{
            res=(res+max(cur-mx2,0LL))%mod;
            break;
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<n;i++){
        cin >> p[i];
        ke[p[i]].push_back(i);
    }
    for (int i=1;i<n;i++)
        cin >> d[i];
    dfs(0);
    build(1,1,n);
    cout << res << '\n';
    cin >> q;
    int v,add;
    while (q--){
        cin >> v >> add;
        walk(v,add);
        update(1,1,n,tin[v],tout[v],add);
        cout << res << '\n';
    }
}

Compilation message

arboras.cpp: In function 'void walk(long long int, long long int)':
arboras.cpp:78:9: warning: unused variable 'tmp' [-Wunused-variable]
   78 |     int tmp=u;
      |         ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 27952 KB Output is correct
2 Correct 147 ms 25928 KB Output is correct
3 Correct 175 ms 26452 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 31096 KB Output is correct
2 Correct 135 ms 34124 KB Output is correct
3 Correct 194 ms 28480 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 256 ms 27952 KB Output is correct
5 Correct 147 ms 25928 KB Output is correct
6 Correct 175 ms 26452 KB Output is correct
7 Correct 190 ms 31096 KB Output is correct
8 Correct 135 ms 34124 KB Output is correct
9 Correct 194 ms 28480 KB Output is correct
10 Correct 175 ms 30540 KB Output is correct
11 Correct 110 ms 34568 KB Output is correct
12 Correct 190 ms 28520 KB Output is correct
13 Correct 135 ms 33348 KB Output is correct
14 Correct 104 ms 36692 KB Output is correct