oj.uz

Submission #875216

# Submission time Handle Problem Language Result Execution time Memory
875216 2023-11-18T19:45:39 Z Ahmed57 Arboras (RMI20_arboras) C++17
0 / 100
 48 ms 44812 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]});
        }
    }
    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));
            if(s[v].size()){
                auto lol = s[v].end();lol--;
                er = (*lol).first;
            }else er = 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 Runtime error 12 ms 19804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 40532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 44812 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -