oj.uz

Submission #875218

# Submission time Handle Problem Language Result Execution time Memory
875218 2023-11-18T19:51:13 Z Ahmed57 Arboras (RMI20_arboras) C++17
0 / 100
 33 ms 22096 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<array<long long,2>> adj[100001];
long long all = 0;long long ans[100001];
pair<long long,long long> par[100001];
long long mod = 1000000007;
multiset<pair<long long,int>> s[100001];
void dfs(int i){
    for(auto j:adj[i]){
        dfs(j[0]);
        if(s[j[0]].size()==0){
            s[i].insert({j[1],j[0]});
        }else{
        auto it = s[j[0]].end();it--;
        s[i].insert({(*it).first+j[1],j[0]});
        }
        ans[i] = max(ans[i],ans[j[0]]+j[1]);
    }
    if(s[i].size()){
    auto it = s[i].end();
    it--;
    all+=(*it).first;
    all%=mod;
    if(s[i].size()>1){
        it--;
        all+=(*it).first;
        all%=mod;
    }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n;
    long long p[n],d[n];
    for(int i = 1;i<n;i++)cin>>p[i];
    for(int i = 1;i<n;i++){
        cin>>d[i];
        adj[p[i]].push_back({i,d[i]});
        par[i] = {p[i],d[i]};
    }
    dfs(0);
    cout<<((all)%mod+mod)%mod<<endl;
    int q;cin>>q;
    while(q--){
        int v,e;
        cin>>v>>e;
        int org = v;
        long long xd = 0,er = 0;
        if(s[v].size()){
            auto it = s[v].end();it--;
            xd = (*it).first;
        }
        er = xd;
        par[v].second+=e;
        while(v!=0){
            xd+=par[v].second;
            er+=par[v].second;
            if(v==org)er-=e;
            int le = v;
            v = par[v].first;
            if(s[v].size()){
                auto it = s[v].end();it--;
                all-=(*it).first;all%=mod;all+=mod;all%=mod;
                if(s[v].size()>1){
                    it--;
                    all-=(*it).first;all%=mod;all+=mod;all%=mod;
                }
            }
            auto it = s[v].lower_bound(make_pair(er,le));
            er = ans[v];
            ans[v] = max(ans[v],xd);
            if(it==s[v].end()){
                cout<<"hh";
                return 0;
            }
            s[v].erase(it);
            s[v].insert({xd,le});
            if(s[v].size()){
                auto it = s[v].end();
    it--;
    all+=(*it).first;
    all%=mod;
    if(s[v].size()>1){
        it--;
        all+=(*it).first;
        all%=mod;
    }
    }
        }
cout<<((all)%mod+mod)%mod<<endl;
    }
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 22096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -