Submission #597294

#	Time	Username	Problem	Language	Result	Execution time	Memory
597294		Deepesson	Arboras (RMI20_arboras)	C++17	24 / 100	5092 ms	10024 KiB

arboras

#include <bits/stdc++.h>
#define MAX 105000

using ll = long long;
typedef std::pair<ll,ll> pii;
struct no_arvore
{

    pii koks[2];

    void insere(pii x){
        ///Se o maior for o x aumenta
        if(koks[0].second==x.second){
            koks[0]=x;
        }else
        ///Se o menor for o y aumenta
        if(koks[1].second==x.second){
            koks[1]=x;
        }else{
            ///Se o maior for menor que o x troca
            if(koks[0].first<x.first){
                koks[1]=koks[0];
                koks[0]=x;
            ///Se o menor for menor que o x troca
            }else if(koks[1].first<x.first){
                koks[1]=x;
            }
        }
        if(koks[0].first<koks[1].first)
            std::swap(koks[0],koks[1]);
    }

    ll peso(void){
        return koks[0].first+koks[1].first;
    }

};

ll peso[MAX];
ll pai[MAX];
no_arvore n[MAX];
pii status[MAX];
std::vector<int> con[MAX];


ll total=0;
ll MOD = 1e9+7;

void atualiza(ll x){
    while(x){
        int cima = pai[x];
        pii novo_peso = {peso[x]+status[x].first,x};
        ll atual = n[cima].peso();
        n[cima].insere(novo_peso);
        ll novo = n[cima].peso();
        ll dif = novo-atual;
        total=(total+dif)%MOD;
        status[cima]=n[cima].koks[0];
        x=cima;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N;
    std::cin>>N;
    for(int i=0;i!=N;++i){status[i].second=i+1;n[i].koks[0].second=i+1;}
    for(int i=0;i!=N-1;++i)std::cin>>pai[i+1];
    for(int i=0;i!=N-1;++i)std::cin>>peso[i+1];
    for(int i=0;i!=N;++i)atualiza(i);
    std::cout<<total<<"\n";
    int Q;
    std::cin>>Q;
    for(int __=0;__!=Q;++__){
        ll a,b;
        std::cin>>a>>b;
        peso[a]+=b;
        atualiza(a);
        std::cout<<total<<"\n";
    }
}

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