oj.uz

Submission #850895

# Submission time Handle Problem Language Result Execution time Memory
850895 2023-09-17T17:02:29 Z alexdd Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 10576 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10576 KB Output is correct
2 Correct 109 ms 9416 KB Output is correct
3 Correct 70 ms 9688 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4696 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 68 ms 10576 KB Output is correct
5 Correct 109 ms 9416 KB Output is correct
6 Correct 70 ms 9688 KB Output is correct
7 Execution timed out 5097 ms 9868 KB Time limit exceeded
8 Halted 0 ms 0 KB -