oj.uz

Submission #597430

# Submission time Handle Problem Language Result Execution time Memory
597430 2022-07-16T02:31:09 Z definitelynotmee Arboras (RMI20_arboras) C++
24 / 100
 5000 ms 26632 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;
const int MOD = 1e9+7;

int main(){
    
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n;

    vector<ll> edge(n);
    vector<int> pai(n);
    matrix<int> g(n);

    for(int i = 1; i < n; i++)
        cin >> pai[i], g[pai[i]].push_back(i);
    for(int i = 1; i < n; i++)
        cin >> edge[i];
    
    vector<multiset<ll,greater<ll>>> s(n,{0,0});

    auto dfs =[&](int id, auto dfs)->void{
        for(int i : g[id]){
            dfs(i,dfs);
            s[id].insert(*s[i].begin() + edge[i]);
        }
    };
    
    dfs(0,dfs);

    ll ans = 0;

    auto calc=[&](int id){
        auto it = s[id].begin();
        ll ret = 0;
        ret+=*it;
        it++;
        ret+=*it;
        return ret;
    };

    vector<ll> resp(n);

    for(int i = 0; i < n; i++){
        resp[i] = calc(i);
        ans+=resp[i];
        ans%=MOD;
    }

    cout << ans << '\n';
    
    cin >> q;

    auto update =[&](int id, ll oldval, ll newval, auto upd)->void{
        ans-=resp[id];
        ll next = *s[id].begin();

        s[id].erase(s[id].find(oldval));
        s[id].insert(newval);

        resp[id] = calc(id);

        ans+=resp[id];
        ans%=MOD;

        // cout << "update " << id << ": " << next << ' ' << resp[id] << endl;
        // cout << "->";
        // for(ll i : s[id])
        //     cout << i << ' ';
        // cout << endl;
        if(id != 0){
            upd(pai[id],next+edge[id],*s[id].begin()+edge[id],upd);
        }
    };

    while(q--){
        ll id, x;
        cin >> id >> x;
        edge[id]+=x;
        update(pai[id],*s[id].begin()+edge[id]-x,*s[id].begin()+edge[id],update);
        cout << ans << '\n';
    }
    

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 21 ms 596 KB Output is correct
3 Correct 5 ms 468 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 25976 KB Output is correct
2 Correct 351 ms 24620 KB Output is correct
3 Correct 533 ms 24884 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Output is correct
2 Correct 21 ms 596 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 239 ms 25976 KB Output is correct
5 Correct 351 ms 24620 KB Output is correct
6 Correct 533 ms 24884 KB Output is correct
7 Execution timed out 5057 ms 26632 KB Time limit exceeded
8 Halted 0 ms 0 KB -