oj.uz

Submission #943599

# Submission time Handle Problem Language Result Execution time Memory
943599 2024-03-11T16:11:01 Z abcvuitunggio Arboras (RMI20_arboras) C++17
100 / 100
 214 ms 37972 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 12892 KB Output is correct
2 Correct 4 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 214 ms 28260 KB Output is correct
2 Correct 133 ms 27240 KB Output is correct
3 Correct 147 ms 27984 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 31056 KB Output is correct
2 Correct 117 ms 35840 KB Output is correct
3 Correct 180 ms 30032 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 214 ms 28260 KB Output is correct
5 Correct 133 ms 27240 KB Output is correct
6 Correct 147 ms 27984 KB Output is correct
7 Correct 167 ms 31056 KB Output is correct
8 Correct 117 ms 35840 KB Output is correct
9 Correct 180 ms 30032 KB Output is correct
10 Correct 178 ms 32080 KB Output is correct
11 Correct 107 ms 36688 KB Output is correct
12 Correct 167 ms 30308 KB Output is correct
13 Correct 107 ms 34896 KB Output is correct
14 Correct 100 ms 37972 KB Output is correct