oj.uz

Submission #597294

# Submission time Handle Problem Language Result Execution time Memory
597294 2022-07-15T20:58:07 Z Deepesson Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 10024 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 6 ms 2872 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10024 KB Output is correct
2 Correct 95 ms 9816 KB Output is correct
3 Correct 71 ms 9784 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 6 ms 2872 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 76 ms 10024 KB Output is correct
5 Correct 95 ms 9816 KB Output is correct
6 Correct 71 ms 9784 KB Output is correct
7 Execution timed out 5092 ms 9044 KB Time limit exceeded
8 Halted 0 ms 0 KB -