oj.uz

Submission #850896

# Submission time Handle Problem Language Result Execution time Memory
850896 2023-09-17T17:04:25 Z alexdd Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 10068 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;

        int init_sum=sum;

        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;

        if(sum==init_sum)
            break;

        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 2 ms 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8672 KB Output is correct
2 Correct 40 ms 7628 KB Output is correct
3 Correct 34 ms 8016 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2406 ms 10068 KB Output is correct
2 Execution timed out 5015 ms 8652 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 4696 KB Output is correct
2 Correct 4 ms 4696 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 52 ms 8672 KB Output is correct
5 Correct 40 ms 7628 KB Output is correct
6 Correct 34 ms 8016 KB Output is correct
7 Correct 2406 ms 10068 KB Output is correct
8 Execution timed out 5015 ms 8652 KB Time limit exceeded
9 Halted 0 ms 0 KB -