Submission #850895

#	Time	Username	Problem	Language	Result	Execution time	Memory
850895		alexdd	Arboras (RMI20_arboras)	C++17	24 / 100	5097 ms	10576 KiB

arboras

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int n;
int parent[100005];
int cost[100005];
pair<int,int> maxd[100005];
vector<int> con[100005];
int sum=0;
void process_update(int a, int b)
{
    int old = maxd[a].first, aux, oldcost = cost[a];
    cost[a]+=b;
    //cout<<a<<" "<<cost[a]<<" zzz\n";
    for(int j=a;j!=1;j=parent[j])
    {
        aux = maxd[parent[j]].first;

        sum = (sum + MOD - (maxd[parent[j]].first + maxd[parent[j]].second)%MOD)%MOD;

        if(maxd[parent[j]].first <= maxd[j].first + cost[j])
        {
            if(maxd[parent[j]].first != old + oldcost)
                maxd[parent[j]].second = maxd[parent[j]].first;
            maxd[parent[j]].first = maxd[j].first + cost[j];
        }
        else if(maxd[parent[j]].second < maxd[j].first + cost[j])
        {
            maxd[parent[j]].second = maxd[j].first + cost[j];
        }
        //cout<<parent[j]<<"   "<<maxd[parent[j]].first<<" "<<maxd[parent[j]].second<<"   "<<old<<" "<<oldcost<<"\n";
        sum = (sum + (maxd[parent[j]].first + maxd[parent[j]].second)%MOD)%MOD;
        old=aux;
        oldcost=cost[parent[j]];
    }
    //cout<<"   ";
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int a;
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        a++;
        parent[i]=a;
        con[parent[i]].push_back(i);
    }
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        process_update(i,a);
    }
    cout<<sum<<"\n";
    int cntq,b;
    cin>>cntq;
    for(int i=0;i<cntq;i++)
    {
        cin>>a>>b;
        a++;
        process_update(a,b);
        cout<<sum<<"\n";
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45