oj.uz

Submission #398526

# Submission time Handle Problem Language Result Execution time Memory
398526 2021-05-04T13:17:15 Z model_code Arboras (RMI20_arboras) C++17
24 / 100
 5000 ms 12624 KB 
/**
* user:  apostol-089
* fname: Daniel Ilie
* lname: Apostol
* task:  Arboras
* score: 24.0
* date:  2020-12-04 10:35:17.572833
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back

const int N = 1e5;
const int MOD = 1e9 + 7;
vector <int> gr[1 + N];
pair <ll, int> dp[1 + N][2];
int ans;
ll d[1 + N];
int p[1 + N];
void add (int &a, ll b) {
    b %= MOD;
    a += b;
    if (a >= MOD)
        a -= MOD;
    if (a < 0)
        a += MOD;
}
void prec (int node) {
    vector <pair <ll, int>> v;
    for (int son : gr[node]) {
        prec (son);
        v.pb ({dp[son][0].first + d[son], son});
    }
    sort (v.begin (), v.end ());
    if (v.size () > 0) {
        dp[node][0] = v.back ();
    }
    if (v.size () > 1)
        dp[node][1] = v[v.size () - 2];
    add (ans, dp[node][0].first);
    add (ans, dp[node][1].first);
}
int main () {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> p[i], p[i]++;
    for (int i = 2; i <= n; i++) {
        cin >> d[i];
        gr[p[i]].pb (i);
    }
    prec (1);
    cout << ans << "\n";
    int q;
    cin >> q;
    while (q--) {
        int v, to_add;
        cin >> v >> to_add; v++;
        d[v] += to_add;
        while (v != 1) {
            int par = p[v];
            ll lstans = 0;
            add (ans, -dp[par][0].first);
            add (ans, -dp[par][1].first);
            if (dp[par][0].second == v)  {
                dp[par][0].first = dp[v][0].first + d[v];
            }
            else {
                if (dp[v][0].first + d[v] >= dp[par][0].first) {
                    dp[par][1] = dp[par][0];
                    dp[par][0] = {dp[v][0].first + d[v], v};
                }
                else {
                    if (dp[v][0].first + d[v] >= dp[par][1].first)
                        dp[par][1] = {dp[v][0].first + d[v], v};
                }
            }
            add (ans, dp[par][0].first);
            add (ans, dp[par][1].first);
            if (ans == lstans) break;
            v = par;
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2764 KB Output is correct
2 Correct 13 ms 2764 KB Output is correct
3 Correct 7 ms 2672 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 10628 KB Output is correct
2 Correct 414 ms 6720 KB Output is correct
3 Correct 343 ms 6528 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2764 KB Output is correct
2 Correct 13 ms 2764 KB Output is correct
3 Correct 7 ms 2672 KB Output is correct
4 Correct 366 ms 10628 KB Output is correct
5 Correct 414 ms 6720 KB Output is correct
6 Correct 343 ms 6528 KB Output is correct
7 Execution timed out 5050 ms 12624 KB Time limit exceeded
8 Halted 0 ms 0 KB -