oj.uz

Submission #875176

# Submission time Handle Problem Language Result Execution time Memory
875176 2023-11-18T18:27:38 Z Ahmed57 Arboras (RMI20_arboras) C++17
0 / 100
 5000 ms 10436 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
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;
void dfs(int i,int pr){
    for(auto j:adj[i]){
        if(j[0]==pr)continue;
        dfs(j[0],i);
        ans[i] = max(ans[i],ans[j[0]]);
    }
    ans[i]+=par[i].second;
    all+=ans[i];all%=mod;
}
int 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,0);
    cout<<((all-ans[0])%mod+mod)%mod<<endl;
    int q;cin>>q;
    while(q--){
        int v,e;
        cin>>v>>e;
        long long xd = ans[v]+e;
        par[v].second+=e;
        ans[v]+=e;
        all+=e;all%=mod;
        while(v!=0){
            v = par[v].first;
            xd+=par[v].second;
            all-=ans[v];all%=mod;all+=mod;all%=mod;
            ans[v] = max(ans[v],xd);
            all+=ans[v];all%=mod;
        }
        cout<<((all-ans[0])%mod+mod)%mod<<endl;
    }
    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5051 ms 10436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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