oj.uz

Submission #635548

# Submission time Handle Problem Language Result Execution time Memory
635548 2022-08-26T12:21:31 Z danikoynov Arboras (RMI20_arboras) C++14
24 / 100
 5000 ms 16316 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

int n, q, par[maxn], lvl[maxn];
ll d[maxn], dp[maxn][2], cl[maxn][2];
vector < pair < int, ll > > g[maxn];

void dfs(int v)
{
    for (pair < int, ll > nb : g[v])
    {
        lvl[nb.first] = lvl[v] + 1;
        dfs(nb.first);
        ll len = nb.second + dp[nb.first][0];
        if (len > dp[v][0])
        {
            dp[v][1] = dp[v][0];
            cl[v][1] = cl[v][0];
            dp[v][0] = len;
            cl[v][0] = nb.first;
        }
        else
        if (len > dp[v][1])
        {
            dp[v][1] = len;
            cl[v][1] = nb.first;
        }
    }
}

ll ans;

void update(int idx, ll dx)
{
    /**int cur_big = idx;
    while(cur_big != 0 && cl[par[cur_big]][0] == cur_big)
        cur_big = par[cur_big];

    int cur_sec = cur_big;
    while(cur_sec != 0 && cl[par[cur_sec]][1] == cur_sec)
        cur_sec = par[cur_sec];


    int new_big = cur_big;
    while(new_big != 0 && dp[new_big][0] + dx > dp[par[new_big]][0])
        new_big = par[new_big];

    int new_sec = cur_sec;
    while(new_sec != 0 && dp[new_sec][0] + dx > dp[par[new_sec]][1])*/

    int cur = idx;
    d[idx] += dx;
    while(true)
    {
        if (cur == 0)
            break;
        ///cout << cur << " " << par[cur] << " " << d[cur] << " " << dp[par[cur]][1] << endl;
        if (dp[cur][0] + d[cur] > dp[par[cur]][0])
        {
            if (cl[par[cur]][0] == cur)
            {
                ans = ans - dp[par[cur]][0];
                dp[par[cur]][0] = dp[cur][0] + d[cur];
                ans = ans + dp[par[cur]][0];
            }
            else
            if (cl[par[cur]][1] == cur)
            {
                ans = ans - dp[par[cur]][1];
                swap(cl[par[cur]][0], cl[par[cur]][1]);
                swap(dp[par[cur]][0], dp[par[cur]][1]);
                dp[par[cur]][0] = dp[cur][0] + d[cur];
                ans = ans + dp[par[cur]][0];
            }
            else
            {
                ans = ans - dp[par[cur]][1];
                cl[par[cur]][1] = cl[par[cur]][0];
                dp[par[cur]][1] = dp[par[cur]][0];
                dp[par[cur]][0] = dp[cur][0] + d[cur];
                ans = ans + dp[par[cur]][0];
                cl[par[cur]][0] = cur;
            }
            cur = par[cur];
        }
        else
        if (dp[cur][0] + d[cur] > dp[par[cur]][1] && cl[par[cur]][0] != cur)
        {
            ///cout << "here" << endl;
            if (cl[par[cur]][1] == cur)
            {
                ans = ans - dp[par[cur]][1];
                dp[par[cur]][1] = dp[cur][0] + d[cur];
                ans = ans + dp[par[cur]][1];
            }
            else
            {
                ans = ans - dp[par[cur]][1];
                dp[par[cur]][1] = dp[cur][0] + d[cur];
                ans = ans + dp[par[cur]][1];
                cl[par[cur]][1] = cur;
            }
            cur = par[cur];
        }
        else
            break;
    }

    ans = ans % mod;
//for (int i = 0; i < n; i ++)
      //  cout << i << " " << dp[i][0] << " " << dp[i][1] << endl;

}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
        cin >> par[i];
    for (int i = 1; i < n; i ++)
    {
        cin >> d[i];
        g[par[i]].push_back({i, d[i]});
    }

    for (int i = 0; i < n; i ++)
        cl[i][0] = cl[i][1] = -1;

    dfs(0);


    for (int i = 0; i <= n; i ++)
    {
        ans = (ans + dp[i][0] + dp[i][1]) % mod;
    }

    cout << ans << endl;

    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int idx;
        ll dx;
        cin >> idx >> dx;
        update(idx, dx);
        cout << ans << endl;
    }
}
int main()
{
    ///freopen("input.txt", "r", stdin);
    solve();
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 10872 KB Output is correct
2 Correct 231 ms 10072 KB Output is correct
3 Correct 226 ms 10968 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 12432 KB Output is correct
2 Execution timed out 5083 ms 16316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct
4 Correct 237 ms 10872 KB Output is correct
5 Correct 231 ms 10072 KB Output is correct
6 Correct 226 ms 10968 KB Output is correct
7 Correct 739 ms 12432 KB Output is correct
8 Execution timed out 5083 ms 16316 KB Time limit exceeded
9 Halted 0 ms 0 KB -