oj.uz

Submission #597424

# Submission time Handle Problem Language Result Execution time Memory
597424 2022-07-16T02:02:16 Z Deepesson Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 11628 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;
      if(!dif)break;
    }
}
 
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 2 ms 2772 KB Output is correct
2 Correct 4 ms 2900 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 59 ms 9928 KB Output is correct
2 Correct 47 ms 11624 KB Output is correct
3 Correct 40 ms 11628 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 10324 KB Output is correct
2 Execution timed out 5039 ms 10836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 59 ms 9928 KB Output is correct
5 Correct 47 ms 11624 KB Output is correct
6 Correct 40 ms 11628 KB Output is correct
7 Correct 1876 ms 10324 KB Output is correct
8 Execution timed out 5039 ms 10836 KB Time limit exceeded
9 Halted 0 ms 0 KB -